分数: 500 点
问题陈述
给你一个无向图 G 与 N 顶点和 M 边缘。 G is 简单 (它没有自环和多重边)和 已连接.
对于 i = 1, 2, \ldots, M, i第一条边是无向边 \lbrace u_i, v_i \rbrace 连接顶点 u_i 和 v_i.
构造两棵生成树 T_1 和 T_2 of G 满足以下两个条件。 (T_1 和 T_2 不一定必须是不同的生成树。)
-
T_1 满足以下条件。
如果我们认为 T_1 作为一棵以顶点为根的有根树 1,对于任何边 \lbrace u, v \rbrace of G 不包含在 T_1,其中之一 u 和 v 是另一个的祖先 T_1.
-
T_2 满足以下条件。
如果我们认为 T_2 作为一棵以顶点为根的有根树 1,没有边缘 \lbrace u, v \rbrace of G 不包含在 T_2 这样其中之一 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
- 输入中的所有值都是整数。
- 给定的图很简单且连通。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印 (2N-2) 行输出 T_1 和 T_2 采用以下格式。 具体来说,
- 的 1-st 通过 (N-1)第行应包含 (N-1) 无向边 \lbrace x_1, y_1\rbrace, \lbrace x_2, y_2\rbrace, \ldots, \lbrace x_{N-1}, y_{N-1}\rbrace 包含在 T_1,每行一个边。
- 的 N-th 通过 (2N-2)第行应包含 (N-1) 无向边 \lbrace z_1, w_1\rbrace, \lbrace z_2, w_2\rbrace, \ldots, \lbrace z_{N-1}, w_{N-1}\rbrace 包含在 T_2,每行一个边。
您可以按任意顺序打印每个生成树中的边缘。 此外,您可以按任意顺序打印每条边的端点。
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}
示例输入 1
6 8 5 1 4 3 1 4 3 5 1 2 2 6 1 6 4 2
示例输出 1
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 不是 Vertex 的祖先 3,反之亦然;
- 边缘 \lbrace 2, 6 \rbrace,顶点 2 不是 Vertex 的祖先 6,反之亦然;
- 边缘 \lbrace 4, 2 \rbrace,顶点 4 不是 Vertex 的祖先 2,反之亦然。
示例输入 2
4 3 3 1 1 2 1 4
示例输出 2
1 2 1 3 1 4 1 4 1 3 1 2
树 T,包含 3 边缘 \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace,是唯一的生成树 G。 由于没有边缘 G 不包含在 T,显然这个 T 满足两个条件 T_1 和 T_2.