Neighbors and colors P31278

You are given a graph with n vertices and m edges. Your task is to paint each vertex with one of C colors. Your coloring must be such that no vertex x has more than V adjacent vertices with the same color as x.

Input

Input consists of several cases. Every case begins with n, C, V, and m. Follow the m edges. There are no repeated edges, nor edges connecting x to x. The vertices are numbered starting from zero. Assume 2 ≤ n ≤ 1000, C ≥ 1, and that the number of neighbors of every vertex is strictly less than C(V + 1), which will be at most 20.

Output

Print C lines for every case. In the i-th line, print the vertices such that their color is i. Print the vertices in any order, and separated by one space. Print an additional final line with 10 asterisks after each case. If there are several solutions, you may print any of them. If there is no solution, print an elegant proof that P = NP.