E - Cables and Servers

Contest Duration: 2025-02-08(Sat) 12:00 - 2025-02-08(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Cables and Servers Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $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$ 回目の操作で選ぶケーブルの番号、繋ぎ変える前に繋がっていたサーバーの番号、繋ぎ変えたあと繋がっているサーバーの番号をこの順に空白区切りで出力せよ。

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1Copy

Copy

出力例 1Copy

Copy

1
1 1 3

ケーブル $1$ のサーバー $1$ に繋がっている側の端をサーバー $3$ に繋ぎ変えることで、サーバー同士がケーブルを介して繋がっている状態にすることができます。

このほか、「ケーブル $5$ のサーバー $4$ に繋がっている側の端をサーバー $1$ に繋ぎ変える」という操作や、「ケーブル $2$ のサーバー $2$ に繋がっている側の端をサーバー $3$ に繋ぎ変える」という操作でもサーバー同士がケーブルを介して繋がっている状態にすることができるため、正解とみなされます。

入力例 2Copy

Copy

出力例 2Copy

Copy

操作をする必要がないこともあります。

入力例 3Copy

Copy

出力例 3Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

No operation may be necessary.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy