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

To check your solution you need to sign in
Sign in to continue