[NICA #3] 图造构

题目描述

从一个 $n$ 个点的无向简单图 $S$(无自环无重边)可以通过以下步骤构造出另一个 $n$ 个点的无向简单图 $T$: 1. 初始 $T$ 中只有 $n$ 个点,没有任何边; 2. 选择 $S$ 中两个度数相同的点 $u,v$,然后在 $T$ 中连接 $u$ 和 $v$,同时将 $S$ 中的点 $u$ 以及 $u$ 连出去的边一同删去; 3. 重复步骤 $2$,直到 $S$ 中仅剩下一个点,此时得到的图 $T$ 即为构造出的图。 容易发现同样的一张无向简单图 $S$ 可能可以构造得出不同的图 $T$,并且我们还可以由构造出来的图 $T$ 继续构造图 $T'$ 等等。 现在给定两张点数相同的无向简单图 $S,T$,请你通过至少 $1$ 次且不超过 $3$ 次构造从 $S$ 构造出 $T$,**输入数据保证有解**。如果有多种方案,输出**任意一种**都会被判定为正确。 或者说你要做 $k(1\le k\le 3)$ 次构造 $S\to T_1\to T_2\to \cdots\to T_k$,满足 $T_k=T$。

输入输出格式

输入格式


输入第一行一个整数 $n$,表示 $S$ 和 $T$ 中点的数量。 输入第二行一个整数 $m_S$,表示 $S$ 中边的数量。 接下来 $m_S$ 行每行两个整数 $u,v$,表示一条 $S$ 中的无向边。保证不存在重边和自环。 输入第 $m_S+3$ 行一个整数 $m_T$,表示 $T$ 中边的数量。 接下来 $m_T$ 行每行两个整数 $u,v$,表示一条 $T$ 中的无向边。同样地,保证不存在重边和自环。

输出格式


输出第一行一个整数 $k$,其中 $1\le k\le 3$,表示你使用的构造次数。 接下来你需要输出 $k(n-1)$ 行,每行两个整数 $u,v$,分别表示你这 $k$ 次构造的构造过程。 具体来说,对于某一次特定的构造过程,你需要输出 $n-1$ 行,表示题意中步骤 $2$ 中每次选择的两个点 $u,v$。

输入输出样例

输入样例 #1

3
3
1 2
2 3
3 1
2
1 2
2 3

输出样例 #1

1
1 2
2 3

说明

#### 样例 1 解释 初始 $T_1$ 有 $n$ 个点,没有边。 一开始 $S$ 中包含三条边 $(1,2),(2,3),(3,1)$,每个点的度数分别为 $d_1=d_2=d_3=2$。 选择 $1,2$ 这两个度数相同的点,然后将边 $(1,2)$ 加入 $T_1$,删除 $S$ 中的边 $(1,2),(3,1)$ 和点 $1$。 此时 $S$ 中包含一条边 $(2,3)$,每个点的度数分别为 $d_2=d_3=1$。 选择 $2,3$ 这两个度数相同的点,然后将边 $(2,3)$ 加入 $T_1$,删除 $S$ 中的边 $(2,3)$ 和点 $2$,并结束此次构造。 此时得到的 $T_1$ 中有两条边 $(1,2),(2,3)$,有 $T_1=T$ 满足条件。 #### 数据范围 对于所有数据,满足 $2\le n\le 10^5$,$1\le m_S,m_T\le 2\times 10^5$。