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. 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. 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). For each test case first print one line with a sing