102923: [Atcoder]ABC292 D - Unicyclic Components

Problem Statement

You are given an undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.

Determine whether every connected component in this graph satisfies the following condition.

• The connected component has the same number of vertices and edges.

Notes

An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If every connected component satisfies the condition, print Yes; otherwise, print No.

Sample Input 1

3 3
2 3
1 1
2 3

Sample Output 1

Yes

The graph has a connected component formed from just vertex $1$, and another formed from vertices $2$ and $3$.
The former has one edge (edge $2$), and the latter has two edges (edges $1$ and $3$), satisfying the condition.

Sample Input 2

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

Sample Output 2

Yes

Sample Input 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

Sample Output 3

No

问题描述

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

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

• 连通分量具有相同数量的顶点和边。

注意

一个 无向图 是没有方向的边的图。
一个图的 子图 是由该图的顶点和边的子集形成的图。
一个图是 连通的 当且仅当可以沿着图中的边在图中的每对顶点之间移动。
一个 连通分量 是一个连通子图，不属于任何更大的连通子图。

约束

• $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