Polish version    English version  
  Reprezentacja -> Relacje z olimpiad


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
Lista reprezentantów
Osiągnięcia
Relacje z olimpiad
BOI 1999
CEOI 1998
CEOI 1997
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: CAV

Jaskinia

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
jednym z prawidłowych wyników jest:
1 5 4 6 8 7 2 3



Wersja do druku