== include(page="template/taskheader" task_id="revolve") ==
Echipa FC Suceava este plecata in cantonament la Paris. Harta metroului din Paris poate fi reprezentata ca un arbore cu N noduri si statia centrala R.
Jucatorii s-au tot plimbat prin oras, si pentru unele trasee directe de la A la B au tinut minte ca nodul cel mai apropiat de statia centrala prin care au trecut era C.
Din pacate, echipa s-a pierdut si pentru a ajunge la stadion la timp si nu a fi retrogradati v-a cerut voua ajutorul: reconstituiti harta metroului din amintirile jucatorului. Daca exista mai multe harti care sa respecte amintirile, atunci puteti afisa oricare dintre ele.
h3. _"Toate drumurile duc in parc."_
(Chirescu, 2016)
h2. Date de intrare
Ionica si Chirescu sunt doi prieteni foarte buni. In tineretile lor, in fiecare zi porneau in Bucuresti in cautarea a ceva de facut. Fiecare dintre ei isi alegea un punct din plecare oarecare si ajungeau, bineinteles, intr-un final, in parcul din Piata Unirii, unde ciocneau un pahar de lapte cald. Traseele lor erau mereu foarte specifice: de fiecare data alegeau drumul cel mai scurt spre parc din punctul in care se aflau. Din fericire pentru acestia, acest lucru era mereu foarte simplu, deoarece harta Bucurestiului era conexa si nu avea niciun ciclu! (cu alte cuvinte, era un arbore)
Deoarece cei doi sunt prieteni foarte buni, de fiecare data cand unul dintre cei doi ajungea intr-un loc in care urma sa ajunga si cel de-al doilea, il astepta cu nerabdare, dupa care isi continuau amandoi drumul linistiti spre parc. Acel loc putea fi fie parcul in sine, fie un loc intermediar.
Acum Ionica si Chirescu sunt adulti responsabili. Chiar astazi s-au intalnit la locuinta rezindentiala a lui Ionica din Silicon Valley si isi rememoreaza amintirile. Acestia isi amintesc $M$ zile (din cele multe pe care le petreceau impreuna). Ei nu isi mai amintesc exact locatia exacta a parcului, dar pentru fiecare zi din cele $M$ cunosc cele doua puncte de plecare $a$, $b$, respectiv *punctul in care cei doi se intalnesc*, notat in problema noastra cu $c$.
h2. Cerinta
Dandu-se numarul de locuri intermediare *$N$*, respectiv numarul de zile, *$M$*, impreuna cu punctele de plecare si locul de intalnire, reconstituiti harta Bucurestiului din tineretile celor doi prieteni. Cei doi stiu ca solutia nu e neaparat unica, asa ca o accepta pe cea care va place mai mult $:)$. Daca cei doi isi amintesc gresit zilele (ceea ce e foarte probabil), afisati *$-1$*.
Fisierul de intrare revolve.in va contine pe primia linie T, numarul de teste.
Urmeaza T teste, pentru fiecare test avand structura:
h2. Date de intrare
Fişierul de intrare *$revolve.in$* va contine pe primia linie *$T$*, numarul de teste.
Vor urma mai apoi *$T$* configuratii de tipul:
N, numarul de noduri ale hartii.
M, numarul de amintiri ale echipei, urmat de M triplete (A, B, C) cu semnificatia ca cel mai inalt nod de pe drumul de la A la B este C.
* *$N M$* (numarul de locatii intermediare, respectiv numarul de zile)
* *$M$* linii, fiecare continand un triplet de forma *$a b c$*, cu semnificatiile din enunt
h2. Date de ieşire
Fisierul de iesire revolve.out va contine pentru fiecare test:
Pentru fiecare test, afisati in fisierul *$revolve.out$* (pe linii separate, ca in exemplu):
R (radacina arborelui)
N-1 perechi (X, Y) cu semnificatia ca exista o muchie de la X la Y.
* *$B$*, un numar natural ce indica locatia parcului Unirii $(1 <= B <= N)$
* *$N-1$* linii, fiecare linie continand cate o pereche *$a b$* cu semnificatia ca exista un drum direct de la nodul *$a$* la nodul *$b$* $(1 <= a, b <= N)$.
Daca pentru un test nu exista nicio harta posibila, atunci pentru acel test se va afisa -1
Daca nu exista nicio harta posibila, atunci se va afisa *$-1$*
h2. Restricţii
N, M <= 100,000
suma tuturor M-urilor <= 500,000
* $T <= 25$
* $N, M <= 100,000$
* Suma tuturor $M$-urilor este mai mica sau egala cu $500,000$
* Suma tuturor $N$-urilor este mai mica sau egala cu $500,000$
* *Constructia afisata trebuie sa respecte conditiile din enunt!*
* _In toate locatiile intermediare se afla magazine aprovizionate cu lapte proaspat, in caz ca unul din cei doi este nerabdator si isi bea laptele pe drum!_
h2. Exemplu
table(example). |_. revolve.in |_. revolve.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
4 3
1 2 1
2 3 1
3 4 3
2 2
1 2 1
1 2 2
| 1
1 2
1 3
4 3
-1
|
h3. Explicaţie
...
Sunt $2$ teste.
In primul test, o solutie posibila este ca parcul sa fie amplasat in nodul 1, iar celelalte locatii ca in output.
Pana si Ionica se prinde ca in al doilea test, nu exista o harta posibila cu proprietatile din enunt.
== include(page="template/taskfooter" task_id="revolve") ==
