P15568 [COCI 2025/2026 #5] 摆放 / Slaganje

本题满分 $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}$。

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