A permutation $\{p\} = \{p_1, p_2, \dots, p_n\}$ of $1 \sim n$ is called a topological sequence of a tree $T$ with $n$ vertices labeled $1$ to $n$ if and only if for every $1 \le i < n$, there exists exactly one $j > i$ such that there is an edge between $p_i$ and $p_j$.

Given a tree $T$, you need to provide the minimum possible number of topological sequences $\{p^{(1)}\}, \{p^{(2)}\}, \dots, \{p^{(k)}\}$ for this tree, such that there is exactly one tree $T$ for which $\{p^{(1)}\}, \{p^{(2)}\}, \dots, \{p^{(k)}\}$ are all valid topological sequences.

Input

The input is read from standard input.

This problem contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. The following lines contain the test cases.

For each test case, the first line contains a positive integer $n$, representing the size of the given tree. The next $n-1$ lines each contain two positive integers $u, v$, describing an edge in the tree.

Output

Output to standard output.

For each test case, output the first line as a positive integer $k$, representing the number of topological sequences you provide. The next $k$ lines each output a permutation of $1 \sim n$, describing the topological sequences you provided. You must ensure $1 \le k \le n$, that these $k$ topological sequences are all valid topological sequences for the corresponding input tree, and that there is only one tree that satisfies these topological sequences as its valid topological sequences.

Examples

Input 1

2
5
2 3
3 1
5 1
5 4
5
1 4
2 3
3 1
5 3

Output 1

2
2 3 1 5 4
4 5 1 3 2
2
4 1 5 3 2
2 5 3 4 1

Constraints

For all test data, $1 \le T \le 100$, $3 \le n \le 100$, $1 \le u, v \le n$.

There are two test points in this problem.

In particular, for all test points, each test case is generated by choosing uniformly at random from all labeled trees with $n$ vertices.

Scoring

For a specific test case within a test point:

1. You must ensure that $k$ and every number in the sequences you output are positive integers in the range $[1, n]$, otherwise the entire test point will receive 0 points.
2. If any of the sequences you provide is not a valid topological sequence for the given input tree, the score ratio for this test case will be 0.
3. If there exist multiple trees for which these sequences are all valid topological sequences, the score ratio for this test case will be 0.
4. Otherwise, if the optimal solution is $K$ and the number of sequences you constructed is $k$, the score ratio for this test case will be $0.97^{k-K}$.

The score ratio for a test point will be the average of the score ratios of all test cases within that test point. The actual score for a test point will be its total points multiplied by the score ratio.