트리의 자기 동형 사상

정점이 n개인 트리 T가 주어진다. 순열 π = π_1, π_2, ..., π_n은 임의의 정점 쌍 (u, v)에 대해 u와 v 사이에 간선이 있을 필요충분조건이 π_u와 π_v 사이에 간선이 있는 것일 때 T의 자기 동형 사상이라고 한다.

두 순열 α = α_1, α_2, ..., α_n과 β = β_1, β_2, ..., β_n의 합성 γ = α ∘ β는 γ_i = α_{β_i}로 정의한다. 즉 γ = α_{β_1}, α_{β_2}, ..., α_{β_n}이다. T의 자기 동형 사상은 합성에 대해 닫혀 있으므로, α와 β가 T의 자기 동형 사상이면 α ∘ β도 T의 자기 동형 사상이다. 이는 β를 먼저 적용한 뒤 α를 적용하는 것으로 볼 수 있다.

k < n을 만족하는 자기 동형 사상의 집합 P = {π(1), π(2), ..., π(k)}를 구하라. T의 임의의 자기 동형 사상은 P에 속한 순열들의 유한 번의 합성으로 표현할 수 있다.

첫 줄에 트리의 정점 개수를 나타내는 정수 n (2 ≤ n ≤ 50)이 주어진다. 이어지는 n − 1개의 줄에는 각각 간선으로 연결된 두 정점 u_i와 v_i (1 ≤ u_i, v_i ≤ n)를 나타내는 두 정수가 주어진다.

첫 줄에 P에 속한 순열의 개수 k (1 ≤ k < n)를 출력한다. 이어지는 k개의 줄에는 i번째 순열의 값 π_1(i), π_2(i), ..., π_n(i)를 각각 n개의 정수로 출력한다. 조건을 만족하는 집합 P가 여러 개라면 그중 아무것이나 출력하면 된다. 답은 항상 존재한다.