题目描述

Having just completed a course in graph algorithms, Bessie the cow has begun coding her very own graph visualizer! Currently, her graph visualizer is only capable of visualizing rooted trees with nodes of distinct values, and it can only perform one kind of operation: merging.

In particular, a merging operation takes any two distinct nodes in a tree with the same parent and merges them into one node, with value equal to the maximum of the values of the two nodes merged, and children a union of all the children of the nodes merged (if any).

Unfortunately, after Bessie performed some merging operations on a tree, her program crashed, losing the history of the merging operations she performed. All Bessie remembers is the tree she started with and the tree she ended with after she performed all her merging operations.

Given her initial and final trees, please determine a sequence of merging operations Bessie could have performed. It is guaranteed that a sequence exists.

Each input consists of $T$ independent test cases. It is guaranteed that the sum of $N$ over all test cases does not exceed $1000$.

输入格式

The first line contains $T$, the number of independent test cases. Each test case is formatted as follows.

The first line of each test case contains the number of nodes $N$ in Bessie's initial tree, which have values $1\dots N$.

Each of the next $N-1$ lines contains two space-separated node values $v_i$ and $p_i$ indicating that the node with value $v_i$ is a child node of the node with value $p_i$ in Bessie's initial tree.

The next line contains the number of nodes $M$ in Bessie's final tree.

Each of the next $M-1$ lines contains two space-separated node values $v_i$ and $p_i$ indicating that the node with value $v_i$ is a child node of the node with value $p_i$ in Bessie's final tree.

输出格式

For each test case, output the number of merging operations, followed by an ordered sequence of merging operations of that length, one per line.

Each merging operation should be formatted as two distinct space-separated integers: the values of the two nodes to merge in any order.

If there are multiple solutions, output any.

题目大意

定义一棵有根树的一次合并操作为：选择两个具有相同父亲的结点，将其合并成一个节点，新节点的编号为原来的两个节点编号的较大值，新节点的子节点集合为原来的两个节点子节点集合的并集。

Bessie 对一棵具有 $n$ 个节点的有根树进行了若干次合并操作，使这棵树变成了一棵具有 $m$ 个节点的树。但不幸的是，她忘记了她进行了哪些合并操作！

你需要构造出任意一组满足上述条件的合并操作序列。输入数据保证有解（即原状态一定可以通过若干次合并操作变为目标状态）。

注意事项：

• 本题单个测试点内有 $T$ 组测试数据；

• 对于 $100\%$ 的数据，$1\le T\le 100$， $2 \leq M\leq N \leq 1000$，$1 \leq v_i, p_i \leq N$；

• 部分分设置：

  • 对于测试点 $2-6$，满足执行操作前的树和执行操作后的树叶子节点数量相同；
  • 对于测试点 $7-16$，无特殊限制。

翻译自

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

提示

$1\le T\le 100$, $2 \leq N \leq 1000$, $1 \leq v_i, p_i \leq N$,$2 \leq M \leq N$.

• Inputs 2-6: The initial and final trees have the same number of leaves.
• Inputs 7-16: No additional constraints.