Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP7_1D - Separatysci |
Rosjanie próbują doprowadzić do dalszego podziału Ukrainy. W granicach tego kraju znajduje się obecnie n miast połączonych m drogami. Dana sieć dróg jest spójna. Dowódcy wojsk rosyjskich zastanawiają się teraz, które z miast powinni przejąć, żeby dokonać podziału sieci dróg na dwie albo więcej części, a co za tym idzie doprowadzić do kolejnego rozbioru Ukrainy. Wojska ukraińskie muszą jak najszybciej zabezpieczyć te miejscowości. Pomóż im i wyznacz miasta, których przejęcie przez Rosjan spowodowałoby podział sieci dróg.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [3;1000] i m ∈ [2;500000] oznaczające odpowiednio liczbę miast oraz liczbę połączeń między nimi. W kolejnych m liniach znajdują się opisy dróg.
Opis każdej drogi składa się z dwóch liczb a ∈ [0;n-1] i b ∈ [0;n-1] określających numery miast, pomiędzy którymi jest połączenie. Pomiędzy daną parą miast znajduje się co najwyżej jedna droga.
Wyjście
W pierwszej linii wyjścia należy wypisać liczbę miast, które powinny zostać zabezpieczone przez wojska ukraińskie. Następnie w drugiej linii wyjścia powinny zostać wypisane ich numery w porządku rosnącym.
Przykład
Wejście
6 7 0 1 0 2 1 2 2 3 3 4 3 5 4 5
Wyjście
2 2 3
Dodane przez: | Maciej Boniecki |
Data dodania: | 2015-03-21 |
Limit czasu wykonania programu: | 0.5s-1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | VII Mistrzostwa WWSI w Programowaniu |