给定一个由n个点,m条边组成的无向图(注意,此图可能不连通),对任意1 ≤ i ≤ m存在一条边连接u[i], v[i]。回答此图是不是二分图。二分图定义为存在一种给图中每一个点染上黑白两色其中之一的着色方式,使得对每一对有边直接相连的点颜色不同。
输入描述:
第一行输入为N和M,代表无向图的点数和边数。接下来M行,表示M条边,每一行两个整数u[i], v[i],满足1 ≤ u[i], v[i] ≤ n,保证图中无重边,自环。其中保证1 ≤ N, M ≤ 100000


输出描述:
一行字符串,为Yes,或者No。Yes表示输入图是二分图。No表示输入图不是二分图。
示例1

输入

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

输出

Yes

说明

如图,把1, 3, 5点染色为白,2, 4染色为黑,即可满足二分图要求,所以这个图是二分图。
示例2

输入

5 4
1 2
2 3
3 1
4 5

输出

No

说明

1, 2, 3号点无论如何染色都无法满足要求,所以不是二分图。
加载中...