CF1250N.Wires

Polycarpus has a complex electronic device. The core of this device is a circuit board. The board has $10^9$ contact points which are numbered from $1$ to $10^9$. Also there are $n$ wires numbered from $1$ to $n$, each connecting two distinct contact points on the board. An electric signal can pass between wires $A$ and $B$ if:

• either both wires share the same contact point;
• or there is a sequence of wires starting with $A$ and ending with $B$, and each pair of adjacent wires in the sequence share a contact point.

The picture shows a circuit board with $5$ wires. Contact points with numbers $2, 5, 7, 8, 10, 13$ are used. Here an electrical signal can pass from wire $2$ to wire $3$, but not to wire $1$.

Currently the circuit board is broken. Polycarpus thinks that the board could be fixed if the wires were re-soldered so that a signal could pass between any pair of wires.

It takes $1$ minute for Polycarpus to re-solder an end of a wire. I.e. it takes one minute to change one of the two contact points for a wire. Any contact point from range $[1, 10^9]$ can be used as a new contact point. A wire's ends must always be soldered to distinct contact points. Both wire's ends can be re-solded, but that will require two actions and will take $2$ minutes in total.

Find the minimum amount of time Polycarpus needs to re-solder wires so that a signal can pass between any pair of wires. Also output an optimal sequence of wire re-soldering.

波利卡普斯拥有一台复杂的电子设备。该设备的核心是一块电路板。这块电路板上有 $10^9$ 个触点，编号从 $1$ 到 $10^9$。此外，还有 $n$ 根导线，编号从 $1$ 到 $n$，每根导线连接电路板上两个不同的触点。电信号可以在导线 $A$ 和导线 $B$ 之间传输，当且仅当满足以下任一条件：

• 两根导线共享同一个触点；
• 存在一条以导线 $A$ 为起点、以导线 $B$ 为终点的导线序列，且该序列中任意相邻的两根导线均共享一个触点。

图中展示了一块含 $5$ 根导线的电路板。使用的触点编号为 $2, 5, 7, 8, 10, 13$。在此图中，电信号可以从导线 $2$ 传输到导线 $3$，但无法传输到导线 $1$。

目前该电路板已损坏。波利卡普斯认为，若能重新焊接导线，使得任意两根导线之间均可传输电信号，则电路板即可修复。

波利卡普斯重焊一根导线的一端需耗时 $1$ 分钟。即：将某根导线的两个触点之一更换为另一个触点，耗时 $1$ 分钟。任何位于区间 $[1, 10^9]$ 内的触点均可作为新触点使用。一根导线的两端必须始终焊接在两个不同的触点上。一根导线的两端均可被重焊，但这需要两次独立操作，总共耗时 $2$ 分钟。

请计算波利卡普斯为使任意两根导线之间均可传输电信号所需重焊导线的最短时间，并输出一组最优的重焊操作序列。

The input contains one or several test cases. The first input line contains a single integer $t$ — number of test cases. Then, $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of wires. The following $n$ lines describe wires, each line containing two space-separated integers $x_i, y_i$ ($1 \le x_i, y_i \le 10^9$, $x_i \neq y_i$) — contact points connected by the $i$-th wire. A couple of contact points can be connected with more than one wire.

Sum of values of $n$ across all test cases does not exceed $10^5$.

输入包含一个或多个测试用例。第一行输入为一个整数 $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$。

For each test case first print one line with a single integer $k$ — the minimum number of minutes needed to re-solder wires so that a signal can pass between any pair of wires. In the following $k$ lines print the description of re-solderings. Each re-soldering should be described by three integers $w_j, a_j, b_j$ ($1 \le w_j \le n$, $1 \le a_j, b_j \le 10^9$). Such triple means that during the $j$-th re-soldering an end of the $w_j$-th wire, which was soldered to contact point $a_j$, becomes soldered to contact point $b_j$ instead. After each re-soldering of a wire it must connect two distinct contact points. If there are multiple optimal re-solderings, print any of them.

对于每个测试用例，首先输出一行，包含一个整数 $k$ —— 使得信号能在任意两根导线之间传输所需的最少重焊分钟数。接下来的 $k$ 行描述每次重焊操作。每次重焊操作由三个整数 $w_j, a_j, b_j$（$1 \le w_j \le n$, $1 \le a_j, b_j \le 10^9$）表示。该三元组表示：在第 $j$ 次重焊操作中，第 $w_j$ 根导线原先焊接到接触点 $a_j$ 的一端，被重新焊接到接触点 $b_j$。每次重焊后，该导线必须连接两个不同的接触点。若存在多种最优重焊方案，输出任意一种即可。