Piggy（暇な時間に星間接続プロトコル委員会を運営している）は、繊細なハードウェアの難問に直面している。$n$ 個の中継局が $(n-1)$ 本の光ファイバーリンクで接続され、木構造を成す最新の通信網が、ついに展開の準備を整えた。しかし、このシステムを起動するには細心の注意が必要である。

起動プロセスでは、特定の経路に沿ってレーザーパルスを発射する。経路とは、2つの駅を結ぶ唯一の単純なルートとして定義される。委員会を悩ませる「量子逆流干渉（Quantum Backflow Interference）」という壊滅的なリスクを避けるため、以下のプロトコルを厳守しなければならない。

• 伝送経路は一つずつ確立しなければならない。
• 電力サージを防ぐため、新しく確立される各経路は、それ以前の経路によって既に活性化された駅の集合と、最大で1つの駅しか共有してはならない。

形式的に、$S$ を現在活性化されている駅の集合とする。駅の集合 $V(P)$ からなる新しい経路 $P$ に対して、条件 $|V(P) \cap S| \le 1$ が満たされなければならない。経路が正常に発射されると、その経路上のすべての駅が活性化された集合 $S$ の一部とみなされる。

あなたの使命は、ネットワーク内のすべての駅を活性化するために必要なレーザーパルスの最小数を求め、法務部門を満足させるような経路の順序を1つ提示することである。

最初の2つのサンプルケースの図。ケース2では、2番目のパルスは最初のパルスと駅2のみを共有しており、非干渉ルールを満たしている。

入力

入力は複数のテストケースからなる。入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 10^4$) が含まれる。各テストケースは以下の通りである。

最初の行には、グリッド内の駅の数を示す整数 $n$ ($2 \le n \le 3 \times 10^5$) が含まれる。

続く $(n-1)$ 行の各行には、駅 $u_i$ と駅 $v_i$ を結ぶ双方向の光ファイバーリンクを表す2つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) が含まれる。

リンクは木を形成し、すべてのテストケースにおける $n$ の総和は $3 \times 10^5$ を超えないことが保証されている。

出力

各テストケースについて、最初の行に経路の最小数 $k$ を出力せよ。続いて、$k$ 行にわたり、シーケンス内の $i$ 番目の経路の端点を表す2つの整数 $a_i$ と $b_i$ を出力せよ。なお、経路が単一の駅で構成される場合、$a_i$ は $b_i$ と等しくてもよい。

複数の最適解が存在する場合、非干渉プロトコルを厳密に守るものであれば、どれでも受け入れられる。

入出力例

入力 1

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

出力 1

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