Malnar 先生订购了一棵拥有 $N$ 个顶点的树，顶点编号为 $1, 2, \dots, N$。不幸的是，Malnar 先生和发送方之间发生了一些误会，导致 Malnar 先生收到了这棵树的 $N$ 个副本。

在等待发送方回复期间，Malnar 先生开始将这些树放置在一个同样用 $1, 2, \dots, N$ 编号的 $N$ 阶正多边形周围。更具体地说，他将每棵树的每个顶点放置在正多边形的某个顶点上，使得属于同一棵树的任意两个顶点都不会被放置在正多边形的同一个顶点上。

Malnar 先生很快发现，正多边形的所有对角线和边都被树的边覆盖了。为了确保这不仅仅是一个巧合，他尝试从头开始再次达到同样的效果。但这对他来说太难了，所以 Malnar 先生请求你的帮助！

形式化地，Malnar 先生正在寻找一组整数 $(p_{i,j})$（$1 \le i, j \le N$），满足：

• 对于每个 $i = 1, \dots, N$，数组 $a_i := p_{i,j}$（$1 \le j \le N$）是整数 $1, 2, \dots, N$ 的一个排列；
• 对于每对 $1 \le i < j \le N$，都存在一个整数 $k$（$1 \le k \le N$），使得顶点 $p_{k,i}$ 和 $p_{k,j}$ 之间的边是原树中的一条边。

可以证明，对于任意一棵树，都存在这样的一组整数。

输入格式

第一行包含一个整数 $N$（$3 \le N \le 2000$），表示树/正多边形的顶点数。

接下来的 $N - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le N$），表示树中由一条边相连的两个顶点的编号。

输出格式

输出 $N$ 行，表示整数 $(p_{i,j})$。

在第 $i$ 行中，依次输出整数 $p_{i,1}, p_{i,2}, \dots, p_{i,N}$。

子任务

样例

输入样例 1

3
1 2
1 3

输出样例 1

2 3 1
1 2 3
3 1 2

输入样例 2

4
1 2
1 3
2 4

输出样例 2

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

输入样例 3

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

输出样例 3

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