题目描述

格林有一棵包含 $n$ 个点的树 $T$，点的编号为 $1$ 到 $n$ 之间的正整数。他会对这棵树执行如下操作：

• 第一步，从 $T$ 中选出一个点 $A$，将所有与点 $A$ 相连的边删除，之后打乱各点的编号。假设得到的森林的形态为 $T_1$。
• 第二步，从 $T$ 中选出一个与 $A$ 不同的点 $B$，将所有与点 $B$ 相连的边删除，之后打乱各点的编号。假设得到的森林的形态为 $T_2$。
• 注意，这两步是相互独立的，即每一步都是在原来的树 $T$ 上进行的。

现在，格林忘记了原来的树是什么样子，但他还记得 $T_1$ 和 $T_2$ 的边集。请你帮助他还原原来的树。

输出任意一棵满足条件的树即可。

输入格式

第一行包含一个正整数 $n$，表示节点数。

接下来有两个部分，分别描述 $T_1$ 和 $T_2$ 的边集。

每个部分的第一行包含一个非负整数 $m$，表示边集大小。接下来 $m$ 行，每行包含两个正整数 $a,b$，表示点 $a$ 与点 $b$ 之间存在一条边。

输出格式

输出 $n-1$ 行，每行包含两个正整数，表示你还原出的树的一条边。

若存在多组解，输出任意一组即可。

样例 1

输入

5
3
1 4
2 1
5 4
1
2 5

输出

2 3
3 4
2 5
2 1

解释

若格林原来的树与样例输出相同，那么点 $A$ 的编号可以为 $1$ 或 $5$，点 $B$ 的编号为 $2$。

数据范围

对于全部测试数据：

$$2\le n\le 2000, \qquad 1\le a,b\le n, \qquad a\ne b.$$

保证给出的边集合法，并且至少存在一组解。

子任务

子任务编号	特殊限制	分值
1	$T$ 是一条链	12
2	$T$ 是一个菊花图	13
3	$n\le 10$	25
4	$n\le 300$，且 $T_1$ 是一棵树	30
5	无	20

提示

下发文件中提供了 checker。你可以编译 checker 得到可执行文件 chk，然后使用以下命令验证输出是否合法：

@下发文件

./chk <input_file> <output_file> <answer_file>