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$.
Let $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$.
You 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$.
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 $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.
## Input
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.
## Output
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.
[samples]
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $.
An automorphism of $ T $ is a permutation $ \pi \in S_n $ such that $ \{u, v\} \in E \iff \{\pi(u), \pi(v)\} \in E $.
Let $ \mathrm{Aut}(T) \subseteq S_n $ denote the automorphism group of $ T $.
**Constraints**
1. $ 2 \leq n \leq 50 $
2. $ T $ is a tree with $ n-1 $ edges given as input.
**Objective**
Find a generating set $ P = \{\pi^{(1)}, \pi^{(2)}, \dots, \pi^{(k)}\} \subseteq \mathrm{Aut}(T) $ such that:
- $ 1 \leq k < n $,
- $ \langle P \rangle = \mathrm{Aut}(T) $, i.e., every automorphism of $ T $ is a finite composition of permutations in $ P $.
Output any such set $ P $.