{"raw_statement":[{"iden":"statement","content":"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$.\n\nLet $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 compose 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 compose beta$ is its automorphism as well. Indeed, it may be conceived as if we firstly applied automorphism $beta$ and then automorphism $alpha$.\n\nYou 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$.\n\nThe first line of input contains a single integer $n$ ($2 <= n <= 50$), which is the number of vertices in the tree.\n\nEach 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.\n\nOn the first line, output a single integer $k$ ($1 <= k < n$), which is the number of permutations in the set $P$.\n\nEach of the following $k$ lines should contain $n$ integers each, denoting $i$-th permutation $pi^((i))_1, pi^((i))_2, \\\\dots, pi^((i))_n$.\n\nIf there are several possible sets $P$, output any one of them. It is guaranteed that the answer always exists.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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 $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."},{"iden":"examples","content":"Input2\n1 2\nOutput1\n2 1\nInput3\n1 2\n1 3\nOutput1\n1 3 2\nInput4\n1 2\n1 3\n1 4\nOutput2\n1 3 2 4\n1 4 3 2\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $.  \nAn automorphism of $ T $ is a permutation $ \\pi \\in S_n $ such that $ \\{u, v\\} \\in E \\iff \\{\\pi(u), \\pi(v)\\} \\in E $.  \nLet $ \\mathrm{Aut}(T) \\subseteq S_n $ denote the automorphism group of $ T $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 50 $  \n2. $ T $ is a tree with $ n-1 $ edges given as input.  \n\n**Objective**  \nFind a generating set $ P = \\{\\pi^{(1)}, \\pi^{(2)}, \\dots, \\pi^{(k)}\\} \\subseteq \\mathrm{Aut}(T) $ such that:  \n- $ 1 \\leq k < n $,  \n- $ \\langle P \\rangle = \\mathrm{Aut}(T) $, i.e., every automorphism of $ T $ is a finite composition of permutations in $ P $.  \n\nOutput any such set $ P $.","simple_statement":"Find a small set of permutations (fewer than n) that can generate all symmetries (automorphisms) of a tree by composing them. Output any such set.","has_page_source":false}