Fişierul intrare/ieşire:	dungeon.in, dungeon.out	Sursă	ONI 2018, clasele 11-12, ziua 2
Autor	Eugenie Daniel Posdarascu	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1.25 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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. 


Cerinta

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