18618번 - Tree Automorphisms 스페셜 저지다국어

Let T be a tree on n vertices. We call permutation π = π₁, π₂, . . . , π_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 π_u and π_v.

Let α = α₁, α₂, . . . , α_n and β = β₁, β₂, . . . , β_n be two permutations. Then their composition γ = α ◦ β is defined as γ = α_β1, α_β2, . . . , α_βn, that is, γ_i = α_βi. Automorphisms of T are closed under composition, so if α and β are two automorphisms of T, then α ◦ β is its automorphism as well. Indeed, it may be conceived as if we firstly applied automorphism β and then automorphism α.

You have to find a set of automorphisms P = {π⁽¹⁾, π⁽²⁾, . . . , π^(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 ≤ n ≤ 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 ≤ u_i, v_i ≤ 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 ≤ 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 π₁⁽ⁱ⁾, π₂⁽ⁱ⁾, . . . , π_n⁽ⁱ⁾ .

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