3747. 排序树

输入格式

输入第一行包含一个整数 $T$ ($T\le {10}^5$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1\le n\le {10}^6$)，表示树的结点个数。

接下来 $n-1$ 行，每行包含两个整数 $u$, $v$，($1\le u,v\le n$)，表示结点 $u$ 的权值小于结点 $v$ 的权值。

输入保证合法且 $\sum n\le {10}^6$。

输出格式

对于第 $x$ 组数据，第一行输出 Case x: 和一个整数 $m$，表示至少需要添加的关系数量。

接下来 $m$ 行，每行输出两个整数 $u$, $v$，表示结点 $u$ 的权值小于结点 $v$ 的权值。

你可以以任何顺序输出这 $m$ 个要添加的关系，任何符合要求的输出都会被判为正确。

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

Case 1: 2
1 4
4 3
Case 2: 2
1 2
5 6