← 返回 apple 的题目列表Determine Whether an Undirected Graph Is Bipartite
类型：online_judge
Given an undirected graph with n nodes numbered from 0 to n - 1 and m undirected edges, where each edge [u, v] connects nodes u and v, determine whether the graph can be colored using exactly two colors such that every pair of adjacent nodes has different colors.
Output true if possible; otherwise output false.
The graph may be disconnected, so every connected component must be checked.
Input Format
First line: two integers n m
Next m lines: two integers u v, representing an undirected edge
Output Format
Print true or false.
Constraints
1 <= n <= 100000
0 <= m <= 200000
0 <= u, v < n
Example
Input:
4 4
0 1
1 2
2 3
3 0
Output:
true
Example
Input
4 4
0 1
1 2
2 3
3 0
Output
true