dungeon

Dungeon

== include(page="template/taskheader" task_id="dungeon") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $dungeon.in$ ...

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 ieşire

h2. Date de iesire

În fişierul de ieşire $dungeon.out$ ...

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. Restricţii

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ţ.

h2. Exemplu
table(example). |_. dungeon.in |_. dungeon.out |

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

| 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

|

h3. Explicaţie
 
...
 

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