E - Cables and Servers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

1 から N の番号がついた N 台のサーバーと 1 から M の番号がついた M 本のケーブルがあります。
ケーブル i はサーバー A_i とサーバー B_i を双方向に結んでいます。

以下の操作を何回か( 0 回でもよい)行うことで、全てのサーバー同士がケーブルを介して繋がっているようにしてください。

  • 操作：ケーブルを 1 つ選び、その片方の端を別のサーバーに繋ぎ変える

操作の最小回数と、最小回数となる操作列を求めてください。

制約

  • 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 行出力せよ。
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

Score : 450 points

Problem Statement

There are N servers numbered from 1 to N and M cables numbered from 1 to M.
Cable i connects servers A_i and B_i bidirectionally.

By performing the following operation some number of times (possibly zero), make all servers connected via cables.

  • Operation: Choose one cable and reconnect one of its ends to a different server.

Find the minimum number of operations required and output an operation sequence achieving this minimum.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Let the minimum number of operations be K. Print K+1 lines.

  • The first line should contain K.
  • The (i+1)-th line should contain three space-separated integers: the number of the cable chosen in the i-th operation, the server number that was originally connected at that end, and the server number to which it is connected after the operation, in this order.

If there are multiple valid solutions, any one of them will be accepted.

Sample Input 1

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

Sample Output 1

1
1 1 3

By reconnecting the end of cable 1 that is connected to server 1 to server 3, the servers can be connected via cables.

図

Operations such as reconnecting the end of cable 5 that is connected to server 4 to server 1, or reconnecting the end of cable 2 that is connected to server 2 to server 3, will also result in all servers being connected and are considered correct.

Sample Input 2

4 3
3 4
4 1
1 2

Sample Output 2

0

No operation may be necessary.

Sample Input 3

5 4
3 3
3 3
3 3
3 3

Sample Output 3

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