4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Cykl Eulera

Cykl Eulera, to taki cykl w grafie, który zawiera każdą krawędź grafu dokładnie raz. Warunkami istnienia cyklu dla grafów nieskierowanych są m.in.:
- spójność grafu;
- spełnienie warunku mówiązce, że z każdego wierzchołka wychodzi parzysta liczba krawędzi.

Twoim zadaniem będzie sprawdzenie, czy dany graf posiada cykl Eulera.
Uwaga: przy budowaniu cyklu, analiza rozpoczynana jest zawsze od wierzchołka z najmniejszym indeksem, tak samo w przypadku wyboru sąsiadów danego wierzchołka. 

Wejś›cie

Wejście zawiera kolejno:

• jeden wiersz tekstu, zawierający liczbę wierzchołków grafu N, 2 ≤ N ≤ 10; 
• N wierszy tekstu, każdy zawierający rozdzielone spacjami numer danego wierzchołka oraz listę numerów jego wierzchołków.
  

Wyjś›cie

• odnaleziony cykl (numery wierzchołków rozdzielone spacjami) albo wartość -1 jeśli w danym grafie cykl Eulera nie istnieje
  

Przykł‚ad

Wejś›cie: 

5
1 2 3
2 1 3 4 5
3 1 2
4 2 5
5 2 4

Wyjście:

1 3 2 5 4 2 1

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 4,0