Bipartite Graph Check
Determine whether a graph can be colored using two colors such that no adjacent nodes share a color.
Input format
The first line contains N and M. The next M lines contain undirected edge pairs.
Output format
Print true if the graph is bipartite, false otherwise. Generate half bipartite and half with odd cycles.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
17 26
2 12
0 8
4 12
3 14
1 13
2 10
0 15
2 14
7 11
3 16
1 16
2 9
4 13
7 13
1 14
6 11
5 16
5 8
7 8
6 12
7 12
7 14
6 10
0 10
5 15
6 15Expected output
trueExample 2
Input
17 3
7 14
6 16
7 15Expected output
true