Tree of Life (hard)

题意翻译

## 题目描述 假设有一棵 $n$ 个点，$n-1$ 条边的树 $T$。 现给定 $k=2$ 张 $n-1$ 个节点的无向图 $G_1,G_2$，满足 $G_1,G_2$ **分别**由 $T$ 删去节点 $a_1,a_2$ 及其连边后打乱标号（用 $1-n$ 中的所有数字给剩余 $n-1$ 个节点两两不同地标号）得到，求 $T$。 $Z$ 组数据。 ## 数据范围 $1\le n\le1000,k=2$。 $1\le Z\le20$。 ## 输入输出格式 ### 输入格式 第一行一个正整数 $Z$，表示数据组数。 接下来，对于每一组数据： 第一行两个正整数 $n,k$，含义如题目所述。 之后，对于每一张无向图： 首先一行一个正整数 $m_i$，表示图 $G_i$ 的边数。 接下来 $m_i$ 行，每行两个正整数 $u,v$，表示图 $G_i$ 中点 $u$ 与点 $v$ 之间有一条边。 保证 $G_i$ 无重边、自环。 ### 输出格式 对于每一组数据： 如果不可能存在满足条件的 $T$，输出一行 `NO`。 否则，输出一行 `YES`，之后按任意顺序输出任意一棵合法的 $T$ 的 $n-1$ 条边。

题目描述

To add insult to injury, the zombies have taken all but two drawings from Heidi! Please help her recover the Tree of Life from only these two drawings.

输入输出格式

输入格式

The input format is the same as in the medium version, except that now the bound on $ n $ is $ 2<=n<=1000 $ and that $ k=2 $ .

输出格式

The same as in the medium version.

输入输出样例

输入样例 #1

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

输出样例 #1

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