== 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$.

 
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.

 
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:
 

 
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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 

| 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") ==
 

 
== include(page="template/taskfooter" task_id="revolve") ==