Two Teams

Difficulty: 1500 4000 ms 128 MB

bfs graphs

Can the people be split into two teams so that every link joins members of different teams (is the graph bipartite)?

Input: the first line has N and M; each of the next M lines has an edge u v (1-based).

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

4 4
1 2
2 3
3 4
4 1

YES

3 3
1 2
2 3
3 1

NO

Read the Editorial