== 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ă, 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.
Poveste şi cerinţă...
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$ ...
h2. Date de iesire
h2. 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.
În fişierul de ieşire $dungeon.out$ ...
h2. Restrictii si precizari
h2. Restricţii
* $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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
== include(page="template/taskfooter" task_id="dungeon") ==
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="dungeon") ==
