← 返回题目列表

AtCoder · abc392_e

H. 电缆和服务器

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

分数: 450 点

问题陈述

有 N 服务器编号自 1 to N 和 M 电缆编号为 1 to M.
电缆 i 连接服务器 A_i 和 B_i 双向。

通过执行以下操作一定次数(可能为零),使所有服务器通过电缆连接。

  • 操作:选择一根电缆并将其一端重新连接到另一台服务器。

找到所需的最小操作数并输出达到该最小值的操作序列。

约束

  • 2 \leq N \leq 2\times 10^5
  • N-1 \leq M \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

输出

设最小操作次数为 K。打印 K+1 行。

  • 第一行应包含 K.
  • 的 (i+1)第行应包含三个空格分隔的整数:在 i- 第一个操作,该端原来连接的服务器编号,以及操作后连接的服务器编号,按此顺序。

如果有多个有效解决方案,则接受其中任何一个。


样本输入 1

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

示例输出 1

1
1 1 3

重新连接电缆末端 1 已连接到服务器 1 到服务器 3,服务器可以通过电缆连接。

図

重新连接电缆末端等操作 5 已连接到服务器 4 到服务器 1,或重新连接电缆末端 2 已连接到服务器 2 到服务器 3也会导致所有服务器都已连接并被认为是正确的。


示例输入 2

4 3
3 4
4 1
1 2

示例输出 2

0

可能不需要任何操作。


示例输入 3

5 4
3 3
3 3
3 3
3 3

示例输出 3

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