406318: GYM102354 J Tree Automorphisms

Let $$$T$$$ be a tree on $$$n$$$ vertices. We call permutation $$$\pi = \pi_1, \pi_2, \dots, \pi_n$$$ an automorphism of $$$T$$$ if, for any pair of vertices $$$(u, v)$$$, there is an edge between them if and only if there is an edge between $$$\pi_u$$$ and $$$\pi_v$$$.

Let $$$\alpha=\alpha_1, \alpha_2, \dots, \alpha_n$$$ and $$$\beta=\beta_1,\beta_2,\dots,\beta_n$$$ be two permutations. Then their composition $$$\gamma = \alpha \circ \beta$$$ is defined as $$$\gamma = \alpha_{\beta_1}, \alpha_{\beta_2}, \dots, \alpha_{\beta_n}$$$, that is, $$$\gamma_i = \alpha_{\beta_i}$$$. Automorphisms of $$$T$$$ are closed under composition, so if $$$\alpha$$$ and $$$\beta$$$ are two automorphisms of $$$T$$$, then $$$\alpha \circ \beta$$$ is its automorphism as well. Indeed, it may be conceived as if we firstly applied automorphism $$$\beta$$$ and then automorphism $$$\alpha$$$.

You have to find a set of automorphisms $$$P=\{\pi^{(1)}, \pi^{(2)}, \dots, \pi^{(k)}\}$$$ such that $$$k < n$$$ and any automorphism of $$$T$$$ may be represented as finite composition of permutations from $$$P$$$.

The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 50$$$), which is the number of vertices in the tree.

Each of the following $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) meaning that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$ in the tree.

On the first line, output a single integer $$$k$$$ ($$$1 \leq k < n$$$), which is the number of permutations in the set $$$P$$$.

Each of the following $$$k$$$ lines should contain $$$n$$$ integers each, denoting $$$i$$$-th permutation $$$\pi^{(i)}_1, \pi^{(i)}_2, \dots, \pi^{(i)}_n$$$.

If there are several possible sets $$$P$$$, output any one of them. It is guaranteed that the answer always exists.

2
1 2

1
2 1

3
1 2
1 3

1
1 3 2

4
1 2
1 3
1 4

2
1 3 2 4
1 4 3 2