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

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

* 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.
h2. Cerinta