给定一张包含 个节点、 条无向边的图(不保证连通)。若存在一种方式可将每个节点染为黑色或白色,使得任意一条边的两个端点颜色不同,则称该图为二分图。 请判断所给图是否为二分图。 【名词解释】 二分图:可将顶点集合划分为两个独立集,且所有边均连接不同集合的图。
输入描述:
第一行输入两个整数 ——节点数与边数。 接下来的 行,每行输入两个整数 ,表示存在一条连接 与 的无向边。保证无重边、自环。


输出描述:
若该图为二分图,输出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号点无论如何染色都无法满足要求,所以不是二分图。
加载中...