解题思路

• 二分图充要条件：图中不存在奇环。
• 经典做法：对每个连通分量做 BFS/DFS 染色。起点染 0，邻点染 1，继续扩展；若遇到与已染相邻点颜色相同，则不是二分图。
• 图可能不连通，需从所有未染色点发起遍历；允许孤点。

算法步骤

• 建邻接表（1..n）。
• 颜色数组 color 初始化为 -1（未染色）。

题目描述

给定一个无向图，判断该图是否为二分图。若可将顶点集合划分为两个不相交的子集，使得任意一条边的两个端点分属不同子集，则该图为二分图。

输入格式

• 第一行包含两个整数 n m，表示图的顶点数与边数（顶点从 1 到 n 编号）。
• 接下来 m 行，每行两个整数 u v，表示一条无向边 (u, v)。

输出格式

• 对于每组数据，若图是二分图输出 Yes，否则输出 No。

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

Yes