两棵生成树

题目描述

给定具有 $N$ 个顶点和 $M$ 条边的无向图 $G$。 $G$ 是简单图（没有自环和重边）且连通。

对于 $i = 1, 2, \ldots, M$，第 $i$ 条边是连接顶点 $u_i$ 和 $v_i$ 的无向边 $\{u_i, v_i\}$。

构造满足以下两个条件的 $G$ 的两棵生成树 $T_1$ 和 $T_2$。（$T_1$ 和 $T_2$ 不一定要是不同的生成树。）

$T_1$ 满足以下条件。

若将 $T_1$ 视为以顶点 $1$ 为根的有根树，则对于 $G$ 中任意一条不在 $T_1$ 内的边 $\{u, v\}$，$u$ 和 $v$ 中有一个是另一个在 $T_1$ 中的祖先。

$T_2$ 满足以下条件。

若将 $T_2$ 视为以顶点 $1$ 为根的有根树，则不存在 $G$ 中不在 $T_2$ 内的边 $\{u, v\}$，使得 $u$ 和 $v$ 中有一个是另一个在 $T_2$ 中的祖先。

可以证明满足上述条件的 $T_1$ 和 $T_2$ 总是存在。

输入格式

输入按以下格式从标准输入给出：

N M
u_1 v_1
u_2 v_2
⋮
u_M v_M

输出格式

打印 $2N-2$ 行，按以下格式输出 $T_1$ 和 $T_2$。具体地：

第 $1$ 行到第 $(N-1)$ 行应包含 $T_1$ 中的 $(N-1)$ 条无向边 $\{x_1, y_1\}, \{x_2, y_2\}, \ldots, \{x_{N-1}, y_{N-1}\}$，每行一条边。

第 $N$ 行到第 $(2N-2)$ 行应包含 $T_2$ 中的 $(N-1)$ 条无向边 $\{z_1, w_1\}, \{z_2, w_2\}, \ldots, \{z_{N-1}, w_{N-1}\}$，每行一条边。

你可以按任意顺序输出每棵生成树中的边。另外，每条边的两个端点的输出顺序也可以是任意的。

x_1 y_1
x_2 y_2
⋮
x_{N-1} y_{N-1}
z_1 w_1
z_2 w_2
⋮
z_{N-1} w_{N-1}

样例

6 8
5 1
4 3
1 4
3 5
1 2
2 6
1 6
4 2

1 4
4 3
5 3
4 2
6 2
1 5
5 3
1 4
2 1
1 6

在上面的样例输出中，$T_1$ 是 $G$ 的一棵生成树，包含 $5$ 条边 $\{1, 4\}, \{4, 3\}, \{5, 3\}, \{4, 2\}, \{6, 2\}$。这个 $T_1$ 满足题目描述中的条件。事实上，对于 $G$ 中不在 $T_1$ 内的每条边：

对于边 $\{5, 1\}$，顶点 $1$ 是 $5$ 的祖先；

对于边 $\{1, 2\}$，顶点 $1$ 是 $2$ 的祖先；

对于边 $\{1, 6\}$，顶点 $1$ 是 $6$ 的祖先。

$T_2$ 是 $G$ 的另一棵生成树，包含 $5$ 条边 $\{1, 5\}, \{5, 3\}, \{1, 4\}, \{2, 1\}, \{1, 6\}$。这个 $T_2$ 满足题目描述中的条件。事实上，对于 $G$ 中不在 $T_2$ 内的每条边：

对于边 $\{4, 3\}$，顶点 $4$ 不是顶点 $3$ 的祖先，反之亦然；

对于边 $\{2, 6\}$，顶点 $2$ 不是顶点 $6$ 的祖先，反之亦然；

对于边 $\{4, 2\}$，顶点 $4$ 不是顶点 $2$ 的祖先，反之亦然。

4 3
3 1
1 2
1 4

1 2
1 3
1 4
1 4
1 3
1 2

包含 $3$ 条边 $\{1, 2\}, \{1, 3\}, \{1, 4\}$ 的树 $T$ 是 $G$ 唯一的生成树。 由于 $G$ 中不存在不在 $T$ 内的边，显然这棵 $T$ 同时满足 $T_1$ 和 $T_2$ 的条件。

数据范围

• $2 \le N \le 2 \times 10^5$
• $N-1 \le M \le \min\{2 \times 10^5, N(N-1)/2\}$
• $1 \le u_i, v_i \le N$
• 输入中的所有值均为整数。
• 给定的图是简单且连通的。