8. Aquamarínové guličky

Malá T našla niekoľko modrých guličiek a nanukových paličiek, tak ich začala lepiť dokopy a staviať z nich. Začala tým, že ich pospájala tak, aby každá nanuková palička spája dve guličky, avšak jedna gulička može byť pripojená na ľubovoľne veľa paličiek. Tiež platí, že celé dielo je súvislé, ale ak by sme ľubovoľnú paličku zobrali, rozpadlo by sa na dva kusy.

Po chvíli si však malá T uvedomila, že jej výtvor je príliš veľký a ťažko sa jej prenáša, takže chcela by ho zmenšiť. Existuje však len jeden spôsob, ako je ochotná zmenšiť svoj výtvor – zoberie jednu guličku preč a spolu s ňou aj všetky paličky, ktoré boli k nej prilepené. Je možné, že dielo sa následne rozpadne na niekoľko kusov, čo nie je dobré, preto by T chcela pridať niekoľko nových paličiek spajajúcich dve guličky tak, aby výtvor bol znovu súvislý. Dostane tak útvar, ktorý má o jednu guličku menej. Nie je to však také jednoduché. Keďže narábanie s lepiacou pištoľou je nebezpečné, bolo by dobré tých nových paličiek pridať čo najmenej. Navyše guličky sú rôznych odtieňov modrej a aby bol výsledný útvar pekný, bolo by vhodné, keby nové paličky spájali guličky s podobnými farbami.

Úloha

Malá T má \(n\) guličiek rôznych odtieňov modrej. T očíslovala guličky od najsvetlejšej po najtmavšiu od \(1\) po \(n\). Následne ich pospájala paličkami tak, že ak si predstavíme guličky ako vrcholy a paličky ako hrany medzi nimi, dostaneme strom. Teraz uvažuje nad tým, že jednu z guličiek spolu s paličkami, na ktoré je prilepená, odstráni. Následne chce znovu pozliepať dokopy všetky časti diela (až na odstránenú guličku) čo najmenej paličkami tak, aby bolo znovu súvislé. Kontrast novovytvoreného guličkového diela je súčet rozdielov (v absolútnej hodnote) medzi číslami novopospájaných dvojíc guličiek. T by chcela dosiahnúť čo najmenší kontrast. Hľadá teda spôsob, ako znovu pospájať guličky tak, aby v prvom rade urobila čo najmenej spojov a spomedzi všetkých takýchto spôsobov hľadá ten, kde nové paličky vytvárajú dokopy čo najmenší kontrast.

Nie je si však istá, ako toto urobiť, a preto necháva túto úlohu na vás, šikovných programátorov. A keďže nevie ešte ktorú guličku odstráni, chce, aby ste vypočítali minimálny počet potrebných paličiek a minimálny možný kontrast pre takéto pospájanie pre každú možnú odstránenú guličku. A ideálne by bolo, keby ste jej aj našli návod, ako pozliepať útvar, aby tieto hodnoty dosiahla. Ak existuje viacero riešení s rovnakým kontrastom a počtom pridaných paličiek, vypíšte akékoľvek.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) (\(1 \leq t \leq 10^5\)) udávajúce počet útvarov, pre ktoré máte úlohu riešiť.

Potom nasleduje \(t\) popisov stromov. V prvom riadku každého popisu je \(n\) (\(1 \leq n \leq 10^5\)), počet guličiek a nasleduje \(n-1\) riadkov popisujúcich dvojice guličiek, ktoré sú spojené paličkou. Guličky sú očíslované od \(1\) po \(n\) podľa ich farby, takže kontrast guličiek s číslami \(a\) a \(b\) je \(|a-b|\).

V jednotlivých sadách platia nasledujúce obmedzenia:

Za každú sadu sa dajú získať \(2\) body. Sady \(1\) a \(3\) sú špeciálne – na ich vyriešenie stačí len nájsť minimálny počet paličiek a minimálny dosiahnuteľný kontrast po odstránení každého vrcholu, ale nemusíte nájsť správny návod na dosiahnutie tohto minima.

Formát výstupu

Pre každý z \(t\) problémov treba vypísať \(n\) popisov riešení, jeden pre odstránenie každého z vrcholov. Keďže T ešte nevie ktorú guličku odstráni, chcela by vedieť ako postupovať, bez ohľadu na to ktorý si vyberie. Vypíšte preto postupne riešenia pre prípad že odstráni prvú, druhú, atď. až po \(n\)-tú guličky.

V prvom riadku popisu riešenia vypíšte dve čísla – minimálny počet paličiek ktoré treba pridať aby sme strom zase pospájali (označme si ho \(e\)) a najmenší možný súčet kontrastov pridaných paličiek. Následne vypíšte \(e\) riadkov popisujúcich jeden spôsob, ako tieto hodnoty dosiahnúť – v každom riadku vypíšte čísla dvoch vrcholov, ktoré chcete spojiť. Medzi riešeniami pre jednotlivé vrcholy vypíšte prázdny riadok

Na získanie bodov za sady \(1\) a \(3\) vám stačí len vypísať \(e\), minimálny kontrast a následne \(e\) riadkov, pričom v každom riadku môžu byť ľubovoľné dve čísla. Čiže nikto nebude kontrolovať, či vami nájdený návod funguje.

Príklad

Input:

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

Output:

1 1
3 4

1 1
3 4

0 0

0 0

1 1
5 6

2 2
4 3
4 5

1 1
6 5

0 0

0 0

0 0

Vzorový vstup obsahuje dva stromy, pre ktoré budeme úlohu riešiť. V prvom z nich, keď odstránime vrchol \(1\), strom sa nám rozpadne na dve časti, jedna časť sú vrcholy \(2\) a \(3\) spojené hranou a druhá časť je samostatný vrchol \(4\). Pridaním hrany medzi vrcholy \(3\) a \(4\) strom opravíme. Kontrast tohto pospájania je rovný \(1\). Vieme si rozmyslieť, že menší počet hrán či kontrast nevieme dosiahnuť.