F - Two Spanning Trees
当前没有测试数据。
F - 两个生成树
得分: $500$ 点
问题描述
给定一个简单连通的无向图 $G$，其中包含 $N$ 个顶点和 $M$ 条边。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边是连接顶点 $u_i$ 和 $v_i$ 的无向边 $\lbrace u_i, v_i \rbrace$。
构建两个满足以下条件的生成树 $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$ 中不存在一条边 $\lbrace u, v \rbrace$，其中 $u$ 和 $v$ 中的一个是另一个在 $T_2$ 中的祖先。
我们可以证明总是存在满足上述条件的 $T_1$ 和 $T_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$
- 输入中的所有值均为整数。
- 给定的图是简单连通图。
输入
输入是标准输入，格式如下:
输出
请按以下格式打印 $(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
在上面的示例输出中，$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$ 满足问题描述中的条件。实际上，对于 $G$ 中没有包含在 $T_1$ 中的每条边:
- 对于边 $\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$ 满足问题描述中的条件。实际上，对于 $G$ 中没有包含在 $T_2$ 中的每条边:
- 对于边 $\lbrace 4, 3 \rbrace$，顶点 $4$ 不是顶点 $3$ 的祖先，反之亦然;
- 对于边 $\lbrace 2, 6 \rbrace$，顶点 $2$ 不是顶点 $6$ 的祖先，反之亦然;
- 对于边 $\lbrace 4, 2 \rbrace$，顶点 $4$ 不是顶点 $2$ 的祖先，反之亦然。
4 3
3 1
1 2
1 4
1 2
1 3
1 4
1 4
1 3
1 2
树 $T$ 是图 $G$ 的唯一的生成树，包含了 $3$ 条边 $\lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace$。 由于 $T$ 中包含了 $G$ 的所有边，很显然 $T$ 同时满足 $T_1$ 和 $T_2$ 的条件。