Soluții trimise

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.

Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.