Background

The full score for this problem is $110$.

Problem Description

Mr. Malnar ordered a tree with $N$ vertices, labeled $1,2,\dots,N$. Unfortunately, due to a communication mistake, he received a total of $N$ such trees.

While waiting for a reply, he placed these trees around a regular $N$-gon that also has $N$ vertices, and the polygon vertices are labeled $1,2,\dots,N$. More specifically, for each tree, he places each vertex of the tree onto some vertex of the polygon, and different vertices of the same tree cannot be placed onto the same polygon vertex.

He soon noticed that after doing this, every side and every diagonal of the polygon was “covered” by some tree edge. To make sure this was not a coincidence, he wants to reconstruct a set of placements, but it is too hard, so he asks you for help.

Formally, you need to construct an integer matrix $(p_{ij})$ ($1 \le i,j \le N$) such that: for each $i=1,2,\dots,N$, the sequence $p_{i1},p_{i2},\dots,p_{iN}$ is a permutation of $1,2,\dots,N$; and for any $1 \le i < j \le N$, there exists an integer $k$ such that vertices $p_{k i}$ and $p_{k j}$ are connected by an edge in the original tree.

It can be proven that for any tree, a construction satisfying the conditions always exists.

Input Format

The first line contains an integer $N$ ($3 \le N \le 2000$), representing the number of vertices of the tree/polygon.

The next $N-1$ lines each contain two integers $u,v$ ($1 \le u,v \le N$), representing an edge of the tree.

Output Format

Output $N$ lines. On the $i$-th line, output $p_{i1},p_{i2},\dots,p_{iN}$.

3
1 2
1 3

2 3 1
1 2 3
3 1 2

4
1 2
1 3
2 4

1 4 3 2
3 2 1 4
2 1 4 3
4 3 2 1

8
1 2
1 3
2 4
2 5
3 6
4 7
5 8

8 1 5 4 3 6 2 7
4 3 6 2 7 8 1 5
2 7 8 1 5 4 3 6
1 5 4 3 6 2 7 8
3 6 2 7 8 1 5 4
7 8 1 5 4 3 6 2
6 2 7 8 1 5 4 3
5 4 3 6 2 7 8 1

Hint

Subtasks

Translated by ChatGPT 5