Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | revolve.in, revolve.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Lucian Bicsi | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 66048 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
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.
Date de intrare
Fisierul de intrare revolve.in va contine pe primia linie T, numarul de teste.
Urmeaza T teste, fiecare test avand structura:
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.
Date de ieşire
Fisierul de iesire revolve.out va contine pentru fiecare test:
R (radacina arborelui)
N-1 perechi (X, Y) cu semnificatia ca exista o muchie de la X la Y.
Daca pentru un test nu exista nicio harta posibila, atunci pentru acel test se va afisa -1
Restricţii
1 ≤ T ≤ 16
1 ≤ N ≤ 100.000
0 ≤ M ≤ 100.000
suma valorilor lui M in cadrul unui fisier de intrare ≤ 500.000
Exemplu
| revolve.in | revolve.out |
|---|---|
| 2 8 5 2 3 1 6 5 1 8 7 5 8 4 3 5 4 3 9 8 9 8 4 1 4 3 1 6 5 4 6 5 9 6 5 3 2 5 2 8 5 4 9 4 | 1 2 1 3 1 4 3 5 3 6 1 7 5 8 5 5 1 3 2 5 3 5 4 3 6 5 7 5 8 4 9 4 |
