Two Spanning Trees

题目描述

你将得到一个具有 $N$ 个顶点和 $M$ 条边的无向图 $G$。 $G$ 是 简单的（没有自环和多重边）且 连通的。 对于 $i = 1, 2, \ldots, M$，第 $i$ 条边是连接顶点 $u_i$ 和 $v_i$ 的无向边 $\lbrace u_i, v_i \rbrace$。 构造图 $G$ 的两个生成树 $T_1$ 和 $T_2$，使它们满足下面的两个条件。 （$T_1$ 和 $T_2$ 不一定要互不相同。）

$T_1$ 满足以下条件。

如果把 $T_1$ 看作以顶点 $1$ 为根的根树，则对于 $G$ 中任意不包含在 $T_1$ 中的边 $\lbrace u, v \rbrace$，$u$ 与 $v$ 中的某一个在 $T_1$ 中是另一个的祖先。

$T_2$ 满足以下条件。

如果把 $T_2$ 看作以顶点 $1$ 为根的根树，则不存在 $G$ 中不包含在 $T_2$ 中的边 $\lbrace u, v \rbrace$ 使得 $u$ 与 $v$ 中的某一个在 $T_2$ 中是另一个的祖先。

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

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

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

第 $1$ 行到第 $(N-1)$ 行应包含 $T_1$ 中的 $(N-1)$ 条无向边 $\lbrace x_1, y_1\rbrace, \lbrace x_2, y_2\rbrace, \ldots, \lbrace x_{N-1}, y_{N-1}\rbrace$，每行一条边。 第 $N$ 行到第 $(2N-2)$ 行应包含 $T_2$ 中的 $(N-1)$ 条无向边 $\lbrace z_1, w_1\rbrace, \lbrace z_2, w_2\rbrace, \ldots, \lbrace z_{N-1}, w_{N-1}\rbrace$，每行一条边。

你可以以任意顺序打印每个生成树中的边。 另外，你可以以任意顺序打印每条边的端点。 $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_{N-1}$ $y_{N-1}$ $z_1$ $w_1$ $z_2$ $w_2$ $\vdots$ $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

4 3
3 1
1 2
1 4

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

提示

$2 \leq N \leq 2 \times 10^5$ $N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$ $1 \leq u_i, v_i \leq N$ 输入中的所有数值均为整数。 给定的图是简单且连通的。在上面的样例输出中，$T_1$ 是图 $G$ 的一个包含 $5$ 条边的生成树 $\lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace$。该 $T_1$ 满足题目中的条件。实际上，对于每一条不包含在 $T_1$ 中的 $G$ 的边：

对于边 $\lbrace 5, 1 \rbrace$，顶点 $1$ 是 $5$ 的祖先；
对于边 $\lbrace 1, 2 \rbrace$，顶点 $1$ 是 $2$ 的祖先；
对于边 $\lbrace 1, 6 \rbrace$，顶点 $1$ 是 $6$ 的祖先。

$T_2$ 是图 $G$ 的另一个包含 $5$ 条边的生成树 $\lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace$。该 $T_2$ 满足题目中的条件。实际上，对于每一条不包含在 $T_2$ 中的 $G$ 的边：

对于边 $\lbrace 4, 3 \rbrace$，顶点 $4$ 既不是顶点 $3$ 的祖先，反之亦然； 对于边 $\lbrace 2, 6 \rbrace$，顶点 $2$ 既不是顶点 $6$ 的祖先，反之亦然； 对于边 $\lbrace 4, 2 \rbrace$，顶点 $4$ 既不是顶点 $2$ 的祖先，反之亦然。
生成树 $T$，包含 $3$ 条边 $\lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace$，是该图的唯一生成树。 由于没有不包含在 $T$ 中的图的边，显然该 $T$ 同时满足 $T_1$ 和 $T_2$ 的条件。

标签: AtCoder|abc251F

来源

AtCoder|abc251F