dungeon

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ță

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ții

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.