{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePolycarpus 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: \u003c/p\u003e\u003cul\u003e \u003cli\u003e either both wires share the same contact point; \u003c/li\u003e\u003cli\u003e 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. \u003c/li\u003e\u003c/ul\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/eb1c7746804da75b273d2d4c6c625fca?v\u003d1726343417\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eThe 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$$$.\u003c/span\u003e \u003c/center\u003e\u003cp\u003eCurrently 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.\u003c/p\u003e\u003cp\u003eIt 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\u0027s ends must always be soldered to distinct contact points. Both wire\u0027s ends can be re-solded, but that will require two actions and will take $$$2$$$ minutes in total.\u003c/p\u003e\u003cp\u003eFind 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eSum of values of $$$n$$$ across all test cases does not exceed $$$10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor 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.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n4 7\n4\n1 2\n2 3\n4 5\n5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n1\n2 3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}