← 返回题目列表

AtCoder · abc251_f

I. 两棵生成树

中文机器翻译题面 查看原题

分数: 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.