問題文

国立こゃーそ大学では学祭の準備が進められています。

こゃーそ大学のキャンパスには $N$ 個の広場と $N-1$ 個の道路があります。 各道路はちょうど $2$ つの広場をつないでいます。 $N-1$ 個の道路によって、すべての広場は互いに行き来できるようになっています。 広場には $1$ から $N$ の番号が、道路には $1$ から $N-1$ の番号がついています。

広場 $k$ には $C_k$ 個の道路が接続されていて、それらの番号は $E_{k,1},E_{k,2},\ldots ,E_{k,C_k}$ です。 また、広場 $k$ と道路 $e$ が接続されている場所にはゲート $(k,e)$ が設置されています。

学祭の飾りつけとして、各広場 $k$ に広場の色 $F(k)$を割り当て、また各ゲート $(k,e)$ にゲートの色 $F'(k,e)$ を割り当てます。 色の割り当ては以下の条件を満たすようにします。

• 各道路の両端のゲートの色は相異なる。つまり、 $a\neq b$ ならば $F'(a,e)\neq F'(b,e)$ を満たす。
• 広場の色とその広場に設置されているゲートのゲートの色をペアにしたものは、キャンパス全体で重複がない。つまり、 $(a,b)\neq (c,d)$ ならば $(F(a),F'(a,b))\neq (F(c),F'(c,d))$ を満たす。

最初に色の種類数 $Q$ を決め、広場の色とゲートの色はその $Q$ 色のうちから選ぶものとします。 広場とゲートで同じ色を使っても構いません。

色の種類数 $Q$ の最小値と、それを実現する色の割り当て方を計算してください。

$1$ 回のプログラム実行で $T$ 個のケースを処理してください。

(22:05 追記) 各色は $1$ 以上 $Q$ 以下の整数で表してください。

制約

• $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)$ すなわち、 $1$ つの広場に同じ道路が $2$ 回以上つながっていることはない。
• $E_{i,j}$ $(1 \leq i \leq N, 1 \leq j \leq C_i)$ の値として、 $1,2,\ldots ,N-1$ がちょうど $2$ 回ずつ現れる。
• すべての広場は互いに行き来できる。
• 入力される値はすべて整数
• $2\leq T$ のとき、 $T$ ケースにわたる $N$ の総和は $100\, 000$ を超えない。

入力

まず最初に整数 $T$ が与えられます。 次に、ケースの入力が $T$ 個続けて与えられます。 $1$ つのケースの入力は次の形式で与えられます。

$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}$

出力

各ケースに対して、 $N+1$ 行出力してください。

$1$ 行目には、色の個数 $Q$ を出力してください。

$k+1$ 行目 ($1\leq k\leq N$) には、広場の色 $F(k)$ と、広場 $k$ に隣接するゲートの色 $F'(k,e)$ を、道路の入力順に出力してください。 つまり、次の形式に従ってください。

$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})$

最後に改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

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

出力

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

入力データが表すキャンパスの図を示します。

これに対応して、出力例は次のような色の割り当てを表します。