Fişierul intrare/ieşire:dungeon.in, dungeon.outSursăONI 2018, clasele 11-12, ziua 2
AutorEugenie Daniel PosdarascuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.25 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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ă, 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.

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

Date de iesire

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.

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

Exemplu

dungeon.indungeon.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?