h2. Date de intrare

Fişierul de intrare revolve.in va contine pe primia linie T, numarul de teste.

Fisierul de intrare revolve.in va contine pe primia linie T, numarul de teste.

Urmeaza T teste, pentru 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 C = lca(A, B)

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

Pentru fiecare test, afisati

Fisierul de iesire revolve.out va contine pentru fiecare test:

R (radacina)
N-1 perechi (a, b) cu semnificatia ca exista o muchie de la a la b.

R (radacina arborelui)
N-1 perechi (X, Y) cu semnificatia ca exista o muchie de la X la Y.

Daca nu exista nicio harta posibile, atunci se va afisa -1

Daca pentru un test nu exista nicio harta posibila, atunci pentru acel test se va afisa -1

h2. Restricţii