401522: GYM100488 I Map Coloring

Peter Godunov is ordered to make the map of Syberia. Syberia consists of n regions, some of which eccentrically border on each other. He wants to assign each of them some color but he has only k different paints. Moreover, according to the terms of reference, on the final version of the map two regions must have different color if and only if they are neighbour regions. It's not required to use all the paints. Help Peter to handle the task or he will be beheaded.

The first line contains three integers separated by spaces: n, m and k (1 ≤ n ≤ 1000, , 1 ≤ k ≤ n) — the number of regions in Syberia, the number of pairs of neighbour regions and the number of paints Peter has.

The next m lines contain two integers each: x_j and y_j (1 ≤ x_j, y_j ≤ n, x_j ≠ y_j) — the numbers of the neighbour regions. Each pair of regions occures at most once.

Output n integers c_i separated by spaces (1 ≤ c_i ≤ k), where c_i is a color to paint the i-th region. If it will cost Peter his head, output the only number « - 1».

3 2 2
1 2
2 3

1 2 1

4 4 2
1 2
2 3
3 4
4 1

1 2 1 2

4 4 3
1 2
1 3
1 4
2 3

-1