N. 缩花
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一棵包含 n 个节点的树，你需要对其执行若干次操作，每次操作按如下顺序进行：

  • 指定一个点 r 作为根节点，此次操作后续步骤均以 r 为根节点。
  • 选择一个非根节点 u ，将 u 的所有直接儿子节点连向 u 的边断开，然后连接到 u 的父亲节点上。

定义菊花图为不存在任何长度大于 3 的路径的图，你的目标是通过最少的操作将给定的树变为菊花图，找到可能的 最少 操作次数。

如果至少需要一次操作，你还需要输出最优操作序列（满足操作次数最少）的第一次操作选择的 r 和 u 。如果存在多个最优操作序列，输出任意一组 r 和 u 即可。

Input

第一行输入一个整数 t（1 ≤ t ≤ 104），表示测试用例数量。

对于每个测试用例：

  • 第一行一个整数 n (1 ≤ n ≤ 105)，表示树的节点数。
  • 接下来 n - 1 行，每行两个整数 u, v (1 ≤ u, v ≤ n)，表示树的一条边。

数据保证所有测试用例的 n 总和不超过 105。

Output

对于每个测试用例：

  • 第一行输出一个整数，表示最小的操作次数。
  • 如果至少需要一次操作，在下一行输出两个整数 r 和 u（1 ≤ r, u ≤ n 且 r ≠ u），表示第一次操作选择的根节点 r 和被操作的节点 u。
Examples
Input
3
2
1 2
4
1 2
1 3
1 4
5
1 2
2 3
3 4
3 5
Output
0
0
1
1 3
Input
1
8
1 2
1 3
2 4
2 5
3 6
3 7
3 8
Output
2
1 3