设 $T$ 为一个有 $n$ 个顶点的树。如果对于任意一对顶点 $(u, v)$，当且仅当 $u$ 和 $v$ 之间有边时，$\pi_u$ 和 $\pi_v$ 之间也有边，我们称排列 $\pi = \pi_1, \pi_2, \dots, \pi_n$ 为 $T$ 的一个自同构。

设 $\alpha = \alpha_1, \alpha_2, \dots, \alpha_n$ 和 $\beta = \beta_1, \beta_2, \dots, \beta_n$ 为两个排列。它们的复合 $\gamma = \alpha \circ \beta$ 定义为 $\gamma = \alpha_{\beta_1}, \alpha_{\beta_2}, \dots, \alpha_{\beta_n}$，即 $\gamma_i = \alpha_{\beta_i}$。$T$ 的自同构在复合运算下是封闭的，因此如果 $\alpha$ 和 $\beta$ 是 $T$ 的两个自同构，那么 $\alpha \circ \beta$ 也是 $T$ 的自同构。实际上，这可以理解为先应用自同构 $\beta$，再应用自同构 $\alpha$。

你需要找到一个自同构集合 $P = \{\pi^{(1)}, \pi^{(2)}, \dots, \pi^{(k)}\}$，使得 $k < n$，且 $T$ 的任意自同构都可以表示为 $P$ 中排列的有限次复合。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 50$)，表示树的顶点数。 接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树中顶点 $u_i$ 和 $v_i$ 之间有一条边。

输出格式

第一行输出一个整数 $k$ ($1 \le k < n$)，表示集合 $P$ 中的排列数量。 接下来的 $k$ 行，每行包含 $n$ 个整数，表示第 $i$ 个排列 $\pi^{(i)}_1, \pi^{(i)}_2, \dots, \pi^{(i)}_n$。 如果存在多个可能的集合 $P$，输出其中任意一个即可。题目保证答案一定存在。

样例

样例输入 1

2
1 2

样例输出 1

1
2 1

样例输入 2

3
1 2
1 3

样例输出 2

1
1 3 2

样例输入 3

4
1 2
1 3
1 4

样例输出 3

2
1 3 2 4
1 4 3 2