AT_abc292_d [ABC292D] Unicyclic Components

题目描述

给定一个有 $N$ 个顶点 $M$ 条边的无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

请判断该图的所有连通分量是否都满足以下条件：

• 每个连通分量中包含的顶点数等于边的数量。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

输出格式

如果所有连通分量都满足条件，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3 3
2 3
1 1
2 3

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

Yes

输入输出样例 #3

输入 #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

说明/提示

注释

无向图 指的是边没有方向的图。
一个图的子图是指从原图中选取一些顶点和一些边所形成的图。
图是连通的，表示图中任意两个顶点都可以通过边相互到达。
连通分量是指连通的子图，并且不存在包含它的更大的连通子图。

数据范围

• $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$
• 输入均为整数

样例解释 1

该图有一个仅包含顶点 $1$ 的连通分量和一个包含顶点 $2,3$ 的连通分量。前者包含 $1$ 条边（边 $2$），后者包含 $2$ 条边（边 $1,3$），均满足条件。

由 ChatGPT 4.1 翻译