← 返回 snowflake 的题目列表Three-Colorability of an Undirected Graph
类型：online_judge
Problem: Three-Colorability of an Undirected Graph
Given an undirected graph, determine whether every vertex can be assigned one of three colors such that the two endpoints of every edge have different colors.
The graph may be disconnected. Every connected component must be colored validly.
Input Format
The first line contains two integers n m:
n: number of vertices, labeled from 0 to n - 1
m: number of undirected edges
The next m lines each contain two integers u v, representing an undirected edge (u, v).
Output Format
Print true if the graph can be properly colored using at most three colors; otherwise print false.
Constraints
1 <= n <= 30
0 <= m <= n * (n - 1) / 2
0 <= u, v < n
There are no duplicate edges.
Example 1
Input:
3 3
0 1
1 2
2 0
Output:
true
Example 2
Input:
4 6
0 1
0 2
0 3
1 2
1 3
2 3
Output:
false
Example 3
Input:
6 4
0 1
1 2
3 4
4 5
Output:
true
Example
Input
3 3
0 1
1 2
2 0
Output
true