Graph Coloring
You are given a graph with
v vertices and e edges, along with c available colors. Your task is to determine whether it is possible to color the graph using the given c colors in such a way that no adjacent nodes have the same color.Input
The first line contains three integers
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) and c (1 ≤ c ≤ 10), representing the number of vertices, the number of edges and the number of available colors, respectively.The next
e lines represent the edges of the graph. Each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b), indicating an edge between vertices a and b.Output
Print
YES if it is possible to color the graph using the given c colors without any adjacent nodes having the same color. Otherwise, print NO.Examples
Input | Output |
3 3 3
1 2
2 3
3 1 | YES |
3 3 2
1 2
2 3
3 1 | NO |
4 4 2
1 2
2 3
3 4
4 1 | YES |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB