← 返回题目列表

Codeforces · 1250/N

N. 电线

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

Polycarpus 拥有复杂的电子设备。该装置的核心是电路板。该板有 $$$10^9$$$ 联络点,编号从 $$$1$$$ 到 $$$10^9$$$。还有 $$$n$$$ 电线,编号从 $$$1$$$ 到 $$$n$$$,每条电线连接板上两个不同的接触点。如果满足以下条件,则电信号可以在电线 $$$A$$$ 和 $$$B$$$ 之间传递:

- 两条线共享相同的接触点;
- 或者存在以 $$$A$$$ 开头并以 $$$B$$$ 结尾的电线序列,并且该序列中的每对相邻电线共享一个接触点。

图片显示了带有 $$$5$$$ 电线的电路板。使用编号为 $$$2、5、7、8、10、13$$$ 的接触点。这里,电信号可以从电线 $$$2$$$ 传递到电线 $$$3$$$,但不能传递到电线 $$$1$$$。

目前电路板已损坏。波利卡普斯认为,如果重新焊接电线,那么电路板就可以被固定,这样信号就可以在任何一对电线之间传递。

Polycarpus 重新焊接电线末端需要 $$$1$$$ 分钟。 IE。更换一根电线的两个接触点之一需要一分钟。 $$$[1, 10^9]$$$ 范围内的任何接触点都可以用作新的接触点。电线的末端必须始终焊接到不同的接触点。电线的两端都可以重新出售,但这需要两次操作,总共需要 $$$2$$$ 分钟。

求 Polycarpus 重新焊接电线所需的最短时间,以便信号可以在任意一对电线之间通过。还输出焊线重新焊接的最佳顺序。

输入

输入包含一个或多个测试用例。第一个输入行包含一个整数 $$$t$$$ — 测试用例的数量。然后,$$$t$$$ 测试用例如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 电线数量。以下 $$$n$$$ 行描述电线,每行包含两个以空格分隔的整数 $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$, $$$x_i \neq y_i$$$) — 由第 $$$i$$$ 电线连接的接触点。几个接触点可以与多于一根的电线连接。

所有测试用例中 $$$n$$$ 的值总和不超过 $$$10^5$$$。

输出

对于每个测试用例,首先用单个整数 $$$k$$$ 打印一行 — 重新焊接电线所需的最短分钟数,以便信号可以在任何一对电线之间通过。在下面的 $$$k$$$ 行中打印重新焊接的描述。每次重焊应由三个整数 $$$w_j, a_j, b_j$$$ ($$$1 \le w_j \le n$$$, $$$1 \le a_j, b_j \le 10^9$$$) 描述。这样的三重意味着在第$$$j$$$次重新焊接期间,焊接到接触点$$$a_j$$$的第$$$w_j$$$线的一端改为焊接到接触点$$$b_j$$$。每次重新焊接电线后,必须连接两个不同的接触点。如果有多个最佳重焊,则打印其中任何一个。

示例

输入 #1

2
1
4 7
4
1 2
2 3
4 5
5 6

输出 #1

0
1
2 3 5