ACRush and his friends want to open a party to celebrate the good result of THU in ICPC 2007. They will use all halls in THU for their party. There are 2 kinds of hall: the small and the large one. In each hall, there is an electronic light system, which forms a tree topology to reduce redundant wires.

• In a small hall, the light system is a general tree with n lights. The lights are numbered from 1 to n
• In a large hall, the light system is obtained from k chains of lights, each chain has length t. The first lights of these k chains are connected with a big light at the central stage of the hall. The big light has id 1, the first light of each chain has id from 2 to k+1, then we continue with the second light of each chain, so on...

Take a look at the figure below:

ACRush hopes in every hall, each light has an unique color and so do the wires!

For easier to remember and to hang up lights against the walls, he sets a rule:

• For each hall, we number the color from 0 to n-1, so each light will get a color id in set {0, 1, ..., n-1}.
• Color id of the wire connects i-th light and j-th light uniquely identified by the positive difference between color ids of i-th light and j-th light.

At first view, the rule seems easy, so everyone agrees with him. But it's really tough if the room is quite large, too hard to set colors for lights. After few seconds, ACRush says "So in this hall, the 1-st light should have color 3, the 2-nd one should have color 0,...". Well, how can he do it very fast?

How about you ? Let write a program to help ACRush's friends setting colors for lights in all T halls.

Input

The first line of file is T -- number of halls in THU (0 < T <= 10). The following line is blank. Then, there are the descriptions of T halls.

For each hall, the first line contains one integer kind. kind denotes which kind of the current hall: 1 is a small hall, 2 is a large one.

On next line, there are two cases:

• For Kind 1, first line is n (1 <= n <= 27) -- number of lights. Next n - 1 lines describe wires in this hall. Each line is pair (u, v) -- there is a wire between light u and v (1 <= u, v <= n).
• For Kind 2, only one line contains two numbers k and t (1 <= k, t <= 1000).

There is a blank line after each description.

Output

For each hall, show us n numbers on one line, i-th number is the color id of i-th light. If there are many solutions any of them will be accepted. Otherwise, if there is no solution, all color id should be -1.
The color ids on one line are separated by exactly one blank, and you'd better not print any redundant blanks. There is no blank line after each case.

Example

Input:
2

1
3
1 2
2 3

2
2 1

Output:
0 2 1
0 4 2 1 3