Piggy（他在业余时间管理着星际连接协议委员会）正面临一个棘手的硬件难题。最新的通信网格由 $n$ 个中继站和 $(n - 1)$ 条光纤链路组成，形成了一棵树状结构，目前已准备好投入使用。然而，系统启动时必须格外谨慎。

激活过程涉及沿特定路径发射激光脉冲。路径定义为两个站点之间的唯一简单路径。由于存在“量子回流干扰”（一种让委员会律师彻夜难眠的现象）的灾难性风险，必须严格遵守以下协议：

• 传输路径必须逐一建立。
• 为了防止电涌，每条新建立的路径与之前任何路径已激活的站点集合之间，最多只能共享一个站点。

形式化地，设 $S$ 为当前已激活站点的集合。对于任何包含站点集合 $V(P)$ 的新路径 $P$，必须满足条件 $|V(P) \cap S| \le 1$。一旦路径成功发射，该路径上的所有站点都被视为已激活集合 $S$ 的一部分。

你的任务是确定激活整个网络中所有站点所需的最少激光脉冲数量，并提供满足法律部门要求的一组路径序列。

前两个样例测试用例的示意图。注意在 Case 2 中，第二条脉冲仅与第一条共享站点 2，满足非干扰规则。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。每个测试用例：

第一行包含一个整数 $n$ ($2 \le n \le 3 \times 10^5$)，表示网格中的站点数量。

接下来的 $(n - 1)$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述了站点 $u_i$ 和站点 $v_i$ 之间的一条双向光纤链路。

保证这些链路构成一棵树，且所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，第一行输出最少路径数量 $k$。随后输出 $k$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示序列中第 $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