题目描述

电影剧组在伯明翰拍摄时，主演的车被人偷走了。你作为临时接手案件的警长，需要在乡间路网中设计一套必定能抓住偷车贼的搜捕计划。

乡间共有 $n$ 个城镇，城镇之间的公路构成一棵树。也就是说，共有 $n-1$ 条双向道路，并且任意两个城镇之间都存在唯一一条简单路径。

每天白天，你可以选择两个城镇 $A,B$，它们可以相同。随后警队会检查从 $A$ 到 $B$ 的简单路径上的所有城镇，包括 $A$ 和 $B$ 本身。如果偷车贼在这些城镇中的任意一个，他就会被抓住。

如果当天没有抓住他，那么到了夜里，他可以沿一条道路移动到相邻城镇，也可以停留在原城镇不动。

设这棵树的叶子数量为 $m$，其中叶子指度数为 $1$ 的城镇。你需要给出一个长度恰好为

天的搜捕计划，使得无论偷车贼最初在哪个城镇、每晚如何移动，最终都一定会被抓住。

请为每个测试用例输出这样一份计划。可以证明，在本题限制下一定存在答案。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$，表示城镇数量。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示城镇 $u$ 和 $v$ 之间有一条双向道路。

输出格式

对于每个测试用例，设该树有 $m$ 个叶子。你需要输出恰好

行，每行包含两个整数 $A,B$，表示某一天检查路径 $A$ 到 $B$。

如果你确信更少的操作已经足以抓住偷车贼，也仍然需要补足行数；多余的行可以输出任意合法路径。

数据范围

• $1\le T\le 100$；
• $2\le n\le 2\cdot 10^5$；
• 输入保证每个测试用例给出的图是一棵树；
• 所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

样例 1

输入

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

输出

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

解释

这些路径按测试用例依次给出。若为了阅读在答案之间加入分隔空行，实际提交时不应输出这些空行。