h2. Date de intrare

Fișierul de intrare dungeon.in va conține pe prima linie un număr natural

Fișierul de intrare dungeon.in va conține pe prima linie un număr natural T reprezentând numărul de teste. Pentru fiecare test pe prima linie se află valoarea N. Pe următoarele N-1 linii se găsesc perechi de valori reprezentând capetele muchiilor de culoare albă (valori de la 1 la N). Următoarele N-1 linii conţin perechi de valori ce reprezintă capetele muchiilor de culoare neagră (valori de la N + 1 la 2 ∗ N). Următoarele N perechi de valori reprezintă capetele muchiilor de culoare roşie.
 
h2. Date de iesire
 
Fișierul de ieșire dungeon.out va conține pentru fiecare din cele T teste câte o linie cu 2 ∗ N valori reprezentând succesiunea nodurilor care formează ciclul hamiltonian special al fiecărui graf dat, respectiv valoarea -1 dacă nu există un astfel de ciclu.
 
• N ≤ 50000
• T ≤ 5
• Pentru teste in valoare de 20 puncte se garantează că N ≤ 10
• Pentru alte teste in valoare de 30 puncte se garantează că ambii arbori au forma de lanţ.
 
h2. Exemplu
 
table(example). |_. dungeon.in |_. dungeon.out |
| 2
4
1 2
1 3
3 4
5 6
5 7
5 8
1 5
2 6
3 7
4 8
4
1 2
1 3
3 4
5 6
6 7
5 8
1 7
2 8
3 5
4 6
| -1
1 7 6 4 3 5 8 2
 
|