Tree Automorphisms

Let T be a tree on n vertices. A permutation π = π_1, π_2, ..., π_n is called an automorphism of T if, for any pair of vertices (u, v), there is an edge between u and v if and only if there is an edge between π_u and π_v.

Let α = α_1, α_2, ..., α_n and β = β_1, β_2, ..., β_n be two permutations. Their composition γ = α ∘ β is defined by γ_i = α_{β_i}, so γ = α_{β_1}, α_{β_2}, ..., α_{β_n}. Automorphisms of T are closed under composition, so if α and β are automorphisms of T, then α ∘ β is an automorphism of T as well. It can be viewed as applying β first and then α.

Find a set of automorphisms P = {π(1), π(2), ..., π(k)} with k < n such that every automorphism of T can be represented as a finite composition of permutations from P.

The first line contains a single integer n (2 ≤ n ≤ 50), the number of vertices in the tree. Each of the following n − 1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n), meaning there is an edge between vertices u_i and v_i.

On the first line, print a single integer k (1 ≤ k < n), the number of permutations in P. Each of the following k lines should contain n integers, the values π_1(i), π_2(i), ..., π_n(i) of the i-th permutation. If several valid sets P exist, print any one of them. It is guaranteed that an answer always exists.