题目背景

SCP2019 的赛场上，一道树上的数毁了小 P 的 THU 梦，现在小 P 在 TP 联谊活动上用这一道树上的数也算是圆了半个 THU 梦了。

题目描述

省流版题意：

给定一棵 $n$ 个点编号 $1\sim n$ 的树，每条边上都有一个初始为 $0$ 的数字。你可以进行若干次操作，每次操作形如选择之前从来没有选择过的两个节点 $x,y$，然后将 $x$ 到 $y$ 简单路径上的边上的数字加一，容易发现你最多只能进行 $\lfloor \frac{n}{2}\rfloor$ 次操作。你需要保证操作后所有边上出现次数最多的数字的出现次数最少，如果有多种方案输出任意一种即可。

输入格式

本题有多组测试数据。

输入第一个数 $T$ 表示测试数据组数，接下来依次输入每组测试数据。

对于每组测试数据：

输入第一行一个正整数 $n$ 表示树的节点数量。

接下来 $n-1$ 行每行两个正整数 $u,v$ 描述树上的一条边。保证输入的是一棵树。

输出格式

对于每组测试数据：

输出第一行一个正整数 $k$ 表示你选择进行的操作数量。

接下来 $k$ 行每行输出两个正整数 $x_i,y_i$ 表示你选择进行的一次操作。

你需要保证 $0\le k\le \lfloor\frac{n}{2}\rfloor$ 且 $x_1,y_1,x_2,y_2,\dots,x_k,y_k$ 两两不同且为 $1$ 至 $n$ 的正整数且你的操作方法最优。

样例数据

样例 1 输入

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

样例 1 输出

2
1 6
3 5

子任务

对于所有数据，满足 $1\le T\le 4\times 10^4$，$1\le n\le 10^5$，$1\le \sum n\le 5\times 10^5$，$1\le u,v\le n$，$u\ne v$。

提示

THU 梦实现不了也可以考虑一下它隔壁的下位替代。