Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-03-24 23:41:34.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Bad macro "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.
h2. 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$.
h2. 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$
h2. 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$
h2. Exemplu
table(example). |_. 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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="revolve")"
