H. Teaching Building
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As a student of The Chinese University of Hong Kong, Shenzhen, Little B got lost when entering the teaching building for the first time (because TB is above TC, and TC is above TD). Years later, Little B became the designer of the new campus teaching building, and now he is designing the cross-sectional view of the building.

The new teaching building will have $$$2n$$$ teaching areas, numbered from $$$1$$$ to $$$2n$$$. The designed footprint length is $$$2n$$$ units, and the building height is limited to $$$n + 1$$$ units, meaning that the cross-sectional view can be regarded as an $$$(n + 1) \times (2n)$$$ grid. Each grid point must contain a number from $$$0$$$ to $$$2n$$$. $$$1 \sim 2n$$$ indicates the teaching area number at that position, and $$$0$$$ means that the position does not belong to any teaching area. Each teaching area must be 4-connected* in the cross-sectional view.

Let $$$a_{i,j}$$$ denote the teaching area number at the grid point in the $$$i$$$-th row and $$$j$$$-th column. We say that teaching area $$$x$$$ is above teaching area $$$y$$$ ($$$x \ne y$$$) if there exist $$$i, j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le 2n$$$) such that $$$a_{i, j} = x$$$, $$$a_{i + 1, j} = y$$$.

For structural clarity and elegance, Little B has determined $$$(2n - 1)$$$ relations. The $$$i$$$-th relation is of the form "teaching area $$$x_i$$$ is above teaching area $$$y_i$$$". If we add a directed edge from $$$x_i$$$ to $$$y_i$$$, the $$$2n$$$ teaching areas exactly form a downward tree** rooted at teaching area $$$1$$$.

Now, you need to design a valid cross-sectional view (i.e., assign a teaching area number to each grid cell) such that the directed graph corresponding to this cross-sectional view is exactly the same as the tree given by Little B. (That is, the relationships specified by Little B must be satisfied, while the relationships not specified by Little B must not be satisfied.)

Please output any valid filling scheme, or report that no solution exists.

*4-connected: A set of grid points is called 4-connected if any two points in the set can be connected by a sequence of adjacent (up, down, left, right) grid points that also belong to the set.

**Downward tree: A rooted tree with a specified root, where every edge is directed from the parent to the child (i.e., from the upper level to the lower level). In this problem, the given $$$2n - 1$$$ relations "teaching area $$$x_i$$$ is above teaching area $$$y_i$$$" correspond to directed edges $$$x_i \to y_i$$$, and these edges form a downward tree rooted at $$$1$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 500$$$), indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \le n \le 500$$$).

Then $$$2n - 1$$$ lines follow, each containing two integers $$$x_i, y_i$$$, representing a relation. It is guaranteed that the input forms a downward tree rooted at $$$1$$$.

It is also guaranteed that $$$\sum n \le 2000$$$.

Output

For each test case:

  • If a valid solution exists, output $$$(n + 1)$$$ lines, each containing $$$2n$$$ integers representing the construction. If multiple solutions exist, output any of them.
  • If no solution exists, output a single line containing the string $$$\texttt{No solution}$$$.
Example
Input
1
2
1 2
1 3
2 4
Output
2 1 1 1
2 2 2 3
4 4 0 3