3747. 排序树

单点时限: 10.0 sec

内存限制: 512 MB

前有牛顿瘟疫“家里蹲”发明力学三大定理。

现有 Cuber QQ 新冠肺炎“家里蹲”发明排序树。

排序树是一棵包含 $n$ 个结点的树,树上的每个结点都有一个权值(已知不存在两个相同权值的结点),但是是未知的。排序树所知道的仅仅是每个结点的权值与其相邻的结点的权值的大小关系。

Cuber QQ 在研究后发现,他所发明的排序树并不一定能唯一地确定结点之间两两的大小关系。

所以他现在想知道至少要加多少个关系(边)可以唯一确定所有结点权值的的排序,当然了,你需要给出一个方案,让 Cuber QQ 信服。

输入格式

输入第一行包含一个整数 $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 \leq 10 ^ 6$。

输出格式

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

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

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

样例

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

3 人解决,53 人已尝试。

8 份提交通过,共有 181 份提交。

9.6 EMB 奖励。

创建: 3 月,4 周前.

修改: 3 月,4 周前.

最后提交: 1 天,5 小时前.

来源: EOJ Monthly 2020.3

题目标签