Fie G un graf neorientat cu 2 * N noduri și 3 * N - 2 muchii. Fiecare muchie este colorată în alb, negru sau roșu.
Se garantează următoarele:

• Există N-1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, ..., N. Ele formează un arbore.
• Există N-1 muchii negre. Capetele lor sunt noduri din mulțimea N+1, N+2, ..., 2*N. Ele formează un arbore.
• Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, ..., N și celălalt capăt în mulțimea N+1, N+2, ..., 2*N.

Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod din graf are exact o muchie roșie incidentă.
Numim ciclu hamiltonian special un ciclu care:

• vizitează fiecare nod al grafului exact o dată.
• nu parcurge consecutiv două muchii de aceeași culoare.
• începe din nodul 1, iar prima muchie parcursă este de culoare roșie.

Cerința

Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.

Date de intrare

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.

Date de ieșire

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.

Restricții și precizări

• N ≤ 50 000
• 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ţ.

Exemplu:

dungeon.in

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

dungeon.out

-1
1 7 6 4 3 5 8 2

Explicație

Există două teste. În fiecare test graful are 2*4 noduri şi 3*4-2 muchii (3 muchii de culoare albă, 3 muchii de culoare neagră, respectiv 4 muchii de culoare roşie). În primul graf nu se găseşte un ciclu hamiltonian special.