시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

Let T be a tree on n vertices. We call permutation π = π1, π2, . . . , π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 α = α1, α2, . . . , αn and β = β1, β2, . . . , β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 = {π(1), π(2), . . . , π(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 ui and vi (1 ≤ ui, vi ≤ n) meaning that there is an edge between vertices ui and vi 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 π1(i), π2(i), . . . , πn(i) .

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

예제 입력 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