← 返回题目列表

AtCoder · math_and_algorithm_ao

047. 二分图

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

配点: 1000 点

問題文

顶点数为 N,边数为 您将获得一张 M 的图表。在每个顶点 它们的编号最大为 1 减去 N 。i 第边缘 (1 \leq i \leq M) 是顶点 是 A_i 与 边缘 B_i 双向连接。

如果该图是二部图, Yes 不是二部图。 No ,否则输出

制約

  • 1 \leq N, M \leq 200\,000
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
\vdots
A_M B_M

出力

如果给定的图是二分图, Yes 不是二部图。 No ,否则输出


入力例 1

8 7
1 5
1 6
2 7
3 7
4 6
5 8
6 8

出力例 1

Yes

入力例 2

6 7
1 6
2 6
3 6
2 4
3 5
1 3
1 4

出力例 2

No