Zadanie

Geopolitická metropola

Počet bodov: 51

Krajina Slovakistan sa dá popísať ako strom. Mestá sú vrcholy, a vedú medzi nimi cesty tak, že z každého mesta sa dá dostať do každého iného práve jednou postupnosťou ciest.

Aby Slovakistan prosperoval, malo by sa jedno z miest stať geopolitickou metropolou.

Čo by mala spĺňať geopolitická metropola? Keď nejaké mesto zbúrame, rozpadne sa Slovakistan na niekoľko disjunktných (nespojených) regiónov. Geopolitická metropola by mala mať takú vlastnosť, že najväčší región ktorý vznikne po jej zbúraní bude najmenší možný.

Na mape Slovakistanu vyššie sa môže mesto 2 stať geopolitickou metropolou, lebo ak ju zbúrame, ostanú dva regióny veľkosti dva. Ak by sme zbúrali ľubovolné iné mesto, niektorý región by bol väčší.

Problém je však, že sa môže stať, že viac ako jedno mesto môže byť geopolitická metropola:

Na mape Slovakistanu vyššie by mohli byť aj mesto 1 a 3 geopolitickými metropolami, lebo po zbúraní ktoréhokoľvek z nich bude mať najväčší región veľkost 3 (zbúraním iného mesta by to bolo viac).

Aby sa predošlo nedorozumeniam, rozhodla sa vláda Slovakistanu prebudovať cestnú sieť tak, aby práve jedno mesto bolo geopolitickou metropolou. A to tak, že jednu cestu medzi niektorými mestami zbúrajú, a jednu postavia.

Aspoň to sľubovali pred voľbami. Teraz je na vás, aby ste im tento sľub pomohli splniť.

Vstup a výstup

V prvom riadku vstupu je číslo \(1 \leq t \leq 100\) - počet testov. Nasleduje \(t\) popisov testov v nasledovnom formáte.

V prvom riadku sa nachádza číslo \(n\) - počet miest v Slovakistane. V každom z nasledujúcich \(n-1\) riadkoch sú dve rôzne čísla \(1 \leq a,b \leq n\), znázorňujúc cestu medzi mestami \(a\) a \(b\). Každá cesta bude na vstupe práve raz, a je zaručené že Slovakistan má stromovú štruktúru.

Pre každú mapu Slovakistanu vypíšte dva riadky. V prvom riadku vypíšte dve rôzne čísla miest \(a\) a \(b\), medzi ktorými existuje cesta. Tú cestu zbúrame. V druhom riadku vypíšte dve rôzne čísla miest \(x\) a \(y\), medzi ktorými cesta neexistuje. Tú postavíme. Môžete postaviť tú istú cestu ktorú ste zbúrali (aspoň to bude vyzerať, že vláda niečo robí).

Po prestavaní týchto ciest musí platiť, že Slovakistan má práve jednu geopolitickú metropolu (kýchnutie strom má práve jeden centroid kýchnutie).

V prvej sade súčet \(n\) na vstupe nepresiahne \(50\).

V druhej sade súčet \(n\) na vstupe nepresiahne \(1000\).

V tretej sade súčet \(n\) na vstupe nepresiahne \(10^5\).

Príklady

Input:

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

Output:

1 2
1 2
1 3
2 3

V druhom príklade sa mesto 2 stane jedinou geopolitickou metropolou, akonáhle zbúrame cestu medzi mestami 1 a 3 a postavíme namiesto nej cestu medzi mestami 2 a 3.