{"raw_statement":[{"iden":"statement","content":"从一个 $n$ 个点的无向简单图 $S$（无自环无重边）可以通过以下步骤构造出另一个 $n$ 个点的无向简单图 $T$：\n\n1. 初始 $T$ 中只有 $n$ 个点，没有任何边；\n2. 选择 $S$ 中两个度数相同的点 $u,v$，然后在 $T$ 中连接 $u$ 和 $v$，同时将 $S$ 中的点 $u$ 以及 $u$ 连出去的边一同删去；\n3. 重复步骤 $2$，直到 $S$ 中仅剩下一个点，此时得到的图 $T$ 即为构造出的图。\n\n容易发现同样的一张无向简单图 $S$ 可能可以构造得出不同的图 $T$，并且我们还可以由构造出来的图 $T$ 继续构造图 $T'$ 等等。\n\n现在给定两张点数相同的无向简单图 $S,T$，请你通过至少 $1$ 次且不超过 $3$ 次构造从 $S$ 构造出 $T$，**输入数据保证有解**。如果有多种方案，输出**任意一种**都会被判定为正确。\n\n或者说你要做 $k(1\\le k\\le 3)$ 次构造 $S\\to T_1\\to T_2\\to \\cdots\\to T_k$，满足 $T_k=T$。"},{"iden":"input","content":"输入第一行一个整数 $n$，表示 $S$ 和 $T$ 中点的数量。\n\n输入第二行一个整数 $m_S$，表示 $S$ 中边的数量。\n\n接下来 $m_S$ 行每行两个整数 $u,v$，表示一条 $S$ 中的无向边。保证不存在重边和自环。\n\n输入第 $m_S+3$ 行一个整数 $m_T$，表示 $T$ 中边的数量。\n\n接下来 $m_T$ 行每行两个整数 $u,v$，表示一条 $T$ 中的无向边。同样地，保证不存在重边和自环。"},{"iden":"output","content":"输出第一行一个整数 $k$，其中 $1\\le k\\le 3$，表示你使用的构造次数。\n\n接下来你需要输出 $k(n-1)$ 行，每行两个整数 $u,v$，分别表示你这 $k$ 次构造的构造过程。\n\n具体来说，对于某一次特定的构造过程，你需要输出 $n-1$ 行，表示题意中步骤 $2$ 中每次选择的两个点 $u,v$。"},{"iden":"note","content":"#### 样例 1 解释\n\n初始 $T_1$ 有 $n$ 个点，没有边。\n\n一开始 $S$ 中包含三条边 $(1,2),(2,3),(3,1)$，每个点的度数分别为 $d_1=d_2=d_3=2$。\n\n选择 $1,2$ 这两个度数相同的点，然后将边 $(1,2)$ 加入 $T_1$，删除 $S$ 中的边 $(1,2),(3,1)$ 和点 $1$。\n\n此时 $S$ 中包含一条边 $(2,3)$，每个点的度数分别为 $d_2=d_3=1$。\n\n选择 $2,3$ 这两个度数相同的点，然后将边 $(2,3)$ 加入 $T_1$，删除 $S$ 中的边 $(2,3)$ 和点 $2$，并结束此次构造。\n\n此时得到的 $T_1$ 中有两条边 $(1,2),(2,3)$，有 $T_1=T$ 满足条件。\n\n#### 数据范围\n\n对于所有数据，满足 $2\\le n\\le 10^5$，$1\\le m_S,m_T\\le 2\\times 10^5$。"}],"translated_statement":null,"sample_group":[["3\n3\n1 2\n2 3\n3 1\n2\n1 2\n2 3","1\n1 2\n2 3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}