题目背景

本题满分 $110$。

题目描述

Malnar 先生订购了一棵有 $N$ 个点的树，点标号为 $1,2,\dots,N$。不幸的是由于沟通失误，他收到了总共 $N$ 棵这样的树。

在等待回复期间，他把这些树放置在一个同样有 $N$ 个顶点的正 $N$ 边形周围，正多边形的顶点也标号为 $1,2,\dots,N$。更具体地，对于每一棵树，他把树的每个顶点放到多边形的某个顶点上，要求同一份树的不同顶点不能放到同一个多边形顶点。

他很快发现，这样放置后，多边形的所有边与所有对角线都被某些树边“覆盖”了。为了确认这不是巧合，他想重新构造一组放置方式，但太难了，于是请你帮忙。

形式化地，你需要构造整数矩阵 $(p_{ij})$（$1 \le i,j \le N$），使得：对于每个 $i=1,2,\dots,N$，序列 $p_{i1},p_{i2},\dots,p_{iN}$ 是 $1,2,\dots,N$ 的一个排列；对于任意 $1 \le i < j \le N$，存在一个整数 $k$，使得顶点 $p_{k i}$ 与 $p_{k j}$ 在原树中有一条边相连。

可以证明对任意树都存在满足条件的构造。

输入格式

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

接下来 $N-1$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le N$），表示树的一条边。

输出格式

输出 $N$ 行，第 $i$ 行输出 $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

提示

【子任务】

子任务	分值	限制
$1$	$10$	存在一个顶点 $u$，使得每条边都与 $u$ 相连
$2$	$15$	$N \le 10$
$3$	$20$	树是一条链
$4$	$25$	$N \le 300$
$5$	$40$	无额外限制