← 返回题目列表

AtCoder · abc292_d

G. 单环分量

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个无向图 N 顶点编号 1 to N 和 M 边编号 1 to M。边缘 i 连接顶点 u_i 和顶点 v_i.

确定该图中的每个连通分量是否满足以下条件。

  • 连接的组件具有相同数量的顶点和边。

注释

An 无向图 是一个有无方向边的图。
A 子图 图的 是由该图的顶点和边的子集形成的图。
图表是 已连接 当人们可以通过边在图中的每一对顶点之间移动时。
A 连接的组件 是一个连通子图,不属于任何更大的连通子图。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq u_i \leq v_i \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1
\vdots
u_M v_M

输出

如果每个连接的组件都满足条件,则打印 Yes;否则,打印 No.


示例输入 1

3 3
2 3
1 1
2 3

示例输出 1

Yes

该图有一个仅由顶点形成的连通分量 1,另一个由顶点组成 2 和 3.
前者有一个边缘(边缘 2),后者有两条边(边 1 和 3),满足条件。


示例输入 2

5 5
1 2
2 3
3 4
3 5
1 5

示例输出 2

Yes

示例输入 3

13 16
7 9
7 11
3 8
1 13
11 11
6 11
8 13
2 11
3 3
8 12
9 11
1 11
5 13
3 12
6 9
1 10

示例输出 3

No