Tree Merging

题目描述

Bessie 母牛刚学完一门图算法课程，开始编写她自己的图可视化工具！目前，她的可视化工具只能可视化结点值两两不同的有根树，并且只能执行一种操作：合并。

具体来说，一次合并操作会选择树中任意两个不同结点，要求它们有相同的父结点，然后将它们合并成一个结点。新结点的值等于被合并的两个结点值的最大值；新结点的孩子结点集合是被合并的两个结点的所有孩子结点的并集（如果存在）。

不幸的是，Bessie 在对一棵树执行了一些合并操作后，她的程序崩溃了，丢失了她执行过的合并操作历史。Bessie 只记得她开始时的树，以及在完成所有合并操作后得到的最终树。

给定初始树和最终树，请确定 Bessie 可能执行过的一系列合并操作。保证存在这样的序列。

每个输入包含 $T$（$1\le T\le 100$）个相互独立的测试用例。保证所有测试用例的 $N$ 之和不超过 $1000$。

输入格式

第一行包含 $T$，表示独立测试用例的数量。每个测试用例如下格式给出。

每个测试用例的第一行包含结点数 $N$（$2 \leq N \leq 1000$），表示 Bessie 的初始树有 $N$ 个结点，结点值为 $1\dots N$。

接下来的 $N-1$ 行，每行包含两个用空格分隔的结点值 $v_i$ 和 $p_i$（$1 \leq v_i, p_i \leq N$），表示在 Bessie 的初始树中，值为 $v_i$ 的结点是值为 $p_i$ 的结点的子结点。

下一行包含结点数 $M$（$2 \leq M \leq N$），表示 Bessie 的最终树有 $M$ 个结点。

接下来的 $M-1$ 行，每行包含两个用空格分隔的结点值 $v_i$ 和 $p_i$（$1 \leq v_i, p_i \leq N$），表示在 Bessie 的最终树中，值为 $v_i$ 的结点是值为 $p_i$ 的结点的子结点。

输出格式

对于每个测试用例，先输出合并操作的次数，然后输出一个按顺序排列、长度为该次数的合并操作序列，每个操作一行。

每次合并操作应输出两个不同的、用空格分隔的整数：表示要合并的两个结点的值，顺序任意。

如果有多种解，输出任意一种。

1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 5

4
2 5
4 8
3 8
7 8

提示

SCORING: Inputs 2-6: 初始树与最终树拥有相同数量的叶子结点。 Inputs 7-16: 无额外限制。 Problem credits: Aryansh Shrivastava

标签: USACO|2023|Gold

来源

USACO|2023|Gold