== include(page="template/taskheader" task_id="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.
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ă, cu exceptia primului nod din ciclu, care este si ultimul.
* nu parcurge consecutiv două muchii de aceeași culoare - muchia de intoarcere la primul nod se considera ca este parcursa consecutiv cu prima muchie.
* începe din nodul $1$, iar prima muchie parcursă este de culoare roșie.
h2. Cerinta
Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.
Afișați un ciclu hamiltonian special al grafului $G$ sau constatați că nu există niciun astfel de ciclu.
h2. 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.
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.
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.
h2. Restrictii si precizari
• 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ţ.
* $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
