Problem Statement

Koyaso National University is preparing for its school festival.

The campus of Koyaso University has $N$ plazas and $N-1$ roads. Each road connects exactly $2$ plazas. Using the $N-1$ roads, all plazas can be reached from one another. The plazas are numbered from $1$ to $N$, and the roads are numbered from $1$ to $N-1$.

Plaza $k$ has $C_k$ roads connected to it, and their numbers are $E_{k,1},E_{k,2},\ldots ,E_{k,C_k}$. Also, a gate $(k,e)$ is installed at the place where plaza $k$ and road $e$ are connected.

As festival decoration, you assign a plaza color $F(k)$ to each plaza $k$, and a gate color $F'(k,e)$ to each gate $(k,e)$. The colors must be assigned so that the following conditions are satisfied.

• The gate colors at the two ends of each road are different. That is, if $a\neq b$, then $F'(a,e)\neq F'(b,e)$ holds.
• The pairs consisting of a plaza color and the gate color of a gate installed at that plaza are all distinct across the entire campus. That is, if $(a,b)\neq (c,d)$, then $(F(a),F'(a,b))\neq (F(c),F'(c,d))$ holds.

First, the number of colors $Q$ is decided, and the plaza colors and gate colors are chosen from those $Q$ colors. The same color may be used for both plazas and gates.

Compute the minimum value of the number of colors $Q$ and a color assignment that achieves it.

Process $T$ cases in $1$ program execution.

(Added at 22:05) Represent each color as an integer between $1$ and $Q$, inclusive.

Constraints

• $1\leq T\leq 10\, 000$
• $2\leq N\leq 200\, 000$
• $1 \leq E_{i,j} \leq N-1$
• $E_{i,j} \neq E_{i,k}$ $(1 \leq i \leq N , 1 \leq j \lt k \leq C_i)$; that is, the same road is never connected to $1$ plaza $2$ or more times.
• Among the values of $E_{i,j}$ $(1 \leq i \leq N, 1 \leq j \leq C_i)$, each of $1,2,\ldots ,N-1$ appears exactly $2$ times.
• All plazas can be reached from one another.
• All input values are integers.
• When $2\leq T$, the sum of $N$ over the $T$ cases does not exceed $100\, 000$.

Input

First, an integer $T$ is given. Then, the inputs of the $T$ cases are given in succession. The input of $1$ case is given in the following format.

$N$
$C_1$ $E_{1,1}$ $E_{1,2}$ $\cdots$ $E_{1,C_1}$
$C_2$ $E_{2,1}$ $E_{2,2}$ $\cdots$ $E_{2,C_2}$
$\vdots$
$C_N$ $E_{N,1}$ $E_{N,2}$ $\cdots$ $E_{N,C_N}$

Output

For each case, output $N+1$ lines.

On line $1$, output the number of colors $Q$.

On line $k+1$ ($1\leq k\leq N$), output the plaza color $F(k)$, followed by the colors $F'(k,e)$ of the gates adjacent to plaza $k$, in the input order of the roads. That is, follow the format below.

$Q$
$F(1)$ $F'(1,E_{1,1})$ $F'(1,E_{1,2})$ $\cdots$ $F'(1,E_{1,C_1})$
$F(2)$ $F'(2,E_{2,1})$ $F'(2,E_{2,2})$ $\cdots$ $F'(2,E_{2,C_2})$
$\vdots$
$F(N)$ $F'(N,E_{N,1})$ $F'(N,E_{N,2})$ $\cdots$ $F'(N,E_{N,C_N})$

Print a newline at the end.

Sample

Sample 1

Input

2
3
1 1
2 2 1
1 2
15
1 5
1 2
1 7
1 10
2 3 13
1 6
3 9 14 1
1 8
1 11
2 12 4
3 11 9 5
4 12 10 1 6
3 14 2 7
2 4 13
2 3 8

Output

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

The following figure shows the campuses represented by the input data.

Correspondingly, the sample output represents the following color assignments.