7. Áááá, záplavy

Kde bolo tam bolo, v pradávnom Egypte bola sieť \(n\) hrobiek posvätných hovniválov prepojená \(n-1\) cestičkami. Celý komplex mal krásnu stromovú štruktúru.

Ale táto idylka bola každoročne narušovaná masívnymi záplavami. Záplavy zaplavujú všetko okolo, vrátane hrobiek posvätných hovniválov. Hlavný architekt Dano prišiel za faraónom s famóznou myšlienkou. Čo keby konečne vybudovali tie protipovodňové zábrany z Egyptofondov o ktorých sa už tak dlho hovorí?

Faraón sa poradil so všetkými svojimi kňazmi, a rozhodol, že vôľa vyššej moci je taká, že protipovodňové zábrany vybudujú, ale musia mať tvar obdĺžnika. Navyše, istý hlavný správca hrobiek Čížoš vyhlásil, že keďže treba šetriť, nemôžu postaviť viac ako dve protipovodňové zábrany.

Akoby situácia nebola už príliš komplikovaná, kancelár správy posvätných hovniválov prišiel s požiadavkou, aby boli ochránené hrobky dostupné práve tak, aby sa dalo chodiť na púť a nestratiť sa. Na púť sa vždy ide od nejakej hrobky do inej po predpripravených cestičkách. Aby sa teda pútnici nestratili, navrhoval kancelár mať v dvoch obdĺžnikoch výhradne hrobky na trati púte.

Architekt Dano sa tak chystal pustiť sa do tej namáhavej práce navrhovania, kadiaľ má ísť bariéra, keď zistil že nevie ktorou trasou má vlastne ísť tohtoročná púť. A nebol v tom sám – netušil to ani faraón, ani kňazi, ani Čížoš, ani kancelár. Vlastne jediné, čo sa dozvedel, bolo, že vhodná trasa púte sa niekomu v dostatočnom predstihu prisní! No to by bolo! Teraz musí vymyslieť, ako preusporiadať hrobky, aby vedel na akúkoľvek trasu púte postaviť protipovodňové ochrany.

Pomôžte mu!

Úloha

Toto je interaktívna úloha. Má dve časti.

Existuje \(n\) hrobiek posvätných hovniválov a \(n-1\) cestičiek (ktoré musia existovať aj po premiestneni hrobiek) tvoriacich strom.

Pohrebisko je štvorcová pláň s rozmermi \(n\times n\) a hrobky môžu byť presunuté iba na celočíselné súradnice.

V prvej časti úlohy dostanete popis cestičiek a váš program vypíše rozloženie hrobiek v rovine.

Po postavení pohrebiska sa viacerým rôznym kňazom snívalo, ktorá púť by bola vhodná. Pre každého zistite, kde by mali byť protipovodňové zábrany postavené. Pochopiteľne, dve obdĺžnikové zábrany by sa nemali prekrývať.

Formát vstupu a výstupu

Na prvom riadku vstupu je číslo \(n\) – počet hrobiek, \(n \leq 50\,000\).

Na ďalších \(n-1\) riadkoch je popis cestičiek: na \(i\)-tom riadku sú dve čísla oddelené medzerou, \(a_i\) a \(b_i\), \(1 \leq a_i, b_i \leq n\), \(a_i \neq b_i\).

Následne váš program má vypísať \(n\) riadkov, na každom riadku dve celé čísla, \(x_i\) a \(y_i\) oddelené medzerou. \(0 < x_i, y_i \leq n\). Na \(i-tom\) riadku výstupu by mali byť súradnice, kde postaviť \(i\)-tu hrobku.

Následne na vstupe dostanete niekoľko popisov vysnených pútí. Úloha je online, ďalší popis púte dostanete až po úspešnom vypísaní barikád pre predchádzajúcu.

Keď dostanete na vstupe nulu, znamená to, že ste na všetko správne odpovedali a máte ukončiť program.

Každý sen pozostáva z dvoch čísel hrobiek, v ktorých začína a končí púť.

Odpoveď na každú požiadavku vypíšte v nasledovnom formáte:

V prvom riadku vypíšte číslo \(k\) (\(1 \leq k \leq 2\)) - počet protipovodňových zábran. Následne vypíšte \(k\) riadkov, v každom štyri čísla: \(x_1\), \(y_1\), \(x_2\) a \(y_2\) – súradnice ľavého dolného a pravého horného rohu (v tomto poradí). (\(1 \leq x_1 \leq x_2 \leq n\) a \(1 \leq y_1 \leq y_2 \leq n\)).

Ak ste odpovedali správne, na vstupe dostanete popis ďalšieho sna (alebo 0 označujúcu ukončenie testovania). Ak nie, testovač vypíše -1. Ak sa váš program vtedy neukončí, hrozí, že miesto WA dostanete TLE alebo EXC.

Aby checker fungoval, ako má, je nutné, aby sa po vypísaní pozícií hrobiek a obdĺžnikov výstup presunul z pamäte na štandardný výstup pomocou príkazu cout.flush() v C++ alebo sys.stdout.flush() v Pythone, pre iné jazyky si vyhľadajte.

Hodnotenie

Sú 4 sady vstupov. V polovici z nich tvoria cestičky binárny strom (z každej hrobky idú najviac tri cestičky).

Počet snov v žiadnej sade nepresiahne \(100\,000\).

V prvých dvoch sadách platí, že aj počet hrobiek, aj počet snov je najviac \(1000\).

Príklad

Input:

3       // prvá časť vstupu
1 2
2 3
1 1     // prvá púť
1 3     // druhá púť
0       // ukončenie vstupu

Output:

1 1     // pozície hrobiek
1 2
2 2
1       // odpoveď na prvú otázku
1 1 1 1
2       // odpoveď na druhú otázku
1 1 1 2
2 2 2 2

Prvú púť pokrýva len jednu hrobku. Stačí jedna protipovodňová zábrana, zakrývajúca presne hrobku číslo 1. V druhom prípade môžeme napríklad postaviť prvú zábranu obklopujúcu prvé dve hrobky a druhú obklopujúcu hrobku 3. Znaky ‘//’ sa v skutočnom vstupe a výstupe neobjavia, ani vy ich nevypisujte. Slúžia len na ilustráciu interakcie