题目描述

从一个 $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$。

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

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$。