CEOI'97 - Nowy Sącz

W Bajtocji jest wiele jaskiń. Poniżej przedstawiona jest mapa jednej z nich:

Wszystkie jaskinie w Bajtocji spełniają następujące warunki:

• Wszystkie komnaty i korytarze są na tym samym poziomie.
• Żadne dwa korytarze nie przecinają się.
• Niektóre z komnat są umieszczone na zewnętrzym okręgu - nazywane są zewnętrznymi komnatami.
• Wszystkie pozostałe komnaty leżą wewnątrz zewnętrznego okręgu i nazywają się wewnętrznymi komnatami.
• Jaskinia posiada wejście prowadzące do jednej z zewnętrznych komnat.
• Każda komnata w jaskini posiada dokładnie trzy korytarze prowadzące do innych komnat. Jeżeli komnata jest zewnętrza, to dwa korytarze prowadzą do dwóch sąsiednich zewnętrznych komnat na okręgu i jedna prowadzi do komnaty wewnętrznej.
• Korytarze łączące zewnętrzne komnaty nazywane są zewnętrznymi korytarzami, a reszta wewnętrznymi korytarzami.
• Przy użyciu tylko wewnętrzych korytarzy jest możliwe przejście pomiędzy dowolnymi komnatami, ale jest tylko jedna taka droga przy założeniu, że każda krawędź jest wykorzystywana co najwyżej raz.
• Nie wszystkie korytarze są tak samo trudne do pokonania. Są dwie grupy korytarzy : łatwe i trudne.

Zdecydowano, że wszystkie jaskinie zostaną otwarte dla turystów. Aby zapewnić bezpieczne zwiedzanie, turyści muszą poruszać się zgodnie z oznakowaniem szlaków, które przechodzą przez każdą komnatę dokładnie raz. Wyjątkiem od tej reguły jest wejście, przez które szlak przechodzi dwa razy - podczas wejścia i wyjścia. Szlaki powinny być tak przygotowane, aby przechodziły przez jak najmniejszą liczbę trudnych korytarzy.

Przykład

Rozważ jaskinię przedstawioną na rysunku. Wejście jest w komnacie 1. Trudne korytarze są pogrubione. Szlak 1, 5, 4, 6, 8, 7, 2, 3 nie zawiera trudnych korytarzy. Komnata końcowa - 1, nie jest wypisywana.

Zadanie

Napisz program, który:

• wczyta opis jaskini z pliku CAV.IN;
• znajdzie szlak, który zaczyna się i kończy w komnacie wejściowej i przechodzi przez wszystkie komnaty tylko raz. Musi on również zawierać jak najmniej trudnych korytarzy;
• wypisuje wynik do pliku CAV.OUT

Wejście

W pierwszej linii pliku CAV.IN znajdują się dwie liczby n (3 < n <= 500) i k. n jest liczbą komnat w jaskini, a k to liczba wszystkich zewnętrznych komnat (k >= 3). Komnaty są ponumerowane od 1 do n. Komnata 1 jest komnatą wejściową. Komnaty 1, 2, ..., k to komnaty zewnętrzne (nie muszą występować w tej kolejności na okręgu).

Kolejne 3n / 2 linii zawiera opis korytarzy. Każdy opis składa się z trzech liczb a, b, c. Liczby a i b są numerami komnat połączonych korytarzem. Liczba c jest równa 0 lub 1: 0 oznacza, że korytarz jest prosty, a 1 trudny.

Wyjście

Twój program powinien wypisać ciąg liczb do pliku wynikowego CAV.OUT; Ciąg musi zaczynać się liczbą 1 (wejście do jaskini). Kolejne n - 1 liczb reprezentują komnaty leżące na znalezionym przez Ciebie szlaku.

Przykład

Dla pliku CAV.IN:

8 5
1 3 0
3 2 0
7 3 1
7 2 0
8 7 0
1 8 0
6 8 0
6 4 0
6 5 1
5 4 0
2 4 0
5 1 0

1 5 4 6 8 7 2 3

Wersja do druku