W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtocji jest miast. Niektóre pary miast są połączone dwukierunkowymi drogami. Drogi nie przecinają się poza końcami, w razie konieczności prowadzą tunelami lub estakadami.
Już wkrótce zacznie się znany wyścig kolarski Tour de Bajtocja. Wiadomo, że trasa wyścigu będzie przebiegała drogami Bajtocji, będzie miała początek i koniec w tym samym mieście oraz nie będzie prowadziła żadną drogą więcej niż raz.
Bajtazar jest słynnym bajtockim kibicem, szefem fanklubu drużyny piłkarskiej Bajtusie. Bajtazar i jego klubowi przyjaciele szczerze nienawidzą wyścigów kolarskich. Chcą oni uniemożliwić sytuację, w której trasa wyścigu przebiegałaby przez miasta, w których mieszkają. Aby temu zapobiec, są gotowi zablokować część dróg. Bajtazar wie, w których miastach mieszkają poszczególni członkowie jego klubu. Chce on wyznaczyć minimalną liczbę dróg, jakie trzeba zablokować, tak aby wyścig kolarski nie mógł przebiegać przez żadne z miast, w których mieszka jakiś członek jego klubu (oczywiście, wliczając w to samego Bajtazara). Twoim zadaniem jest pomóc Bajtazarowi w wyznaczeniu takiego zbioru dróg.
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz (, , ), pooddzielane pojedynczymi odstępami, oznaczające odpowiednio: liczbę miast, liczbę dróg oraz liczbę miast, w których mieszkają członkowie klubu. Miasta są ponumerowane od 1 do , przy czym miasta, w których mieszkają członkowie klubu, mają numery od 1 do . W każdym z kolejnych wierszy znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem, i (), oznaczające, że miasta i są połączone dwukierunkową drogą. Każda para miast Bajtocji jest połączona co najwyżej jedną drogą.
W testach wartych łącznie 40% punktów zachodzą dodatkowe warunki i .
Twój program powinien wypisać na standardowe wyjście zbiór dróg o minimalnej liczności, których blokada uniemożliwi zorganizowanie wyścigu kolarskiego przechodzącego przez jakiekolwiek miasto, w którym mieszkają członkowie klubu.
W pierwszym wierszu wyjścia należy wypisać minimalną liczbę dróg, jakie należy zablokować. W kolejnych wierszach powinien znaleźć się opis dróg, które należy zablokować, po jednej drodze w wierszu. Każdą drogę reprezentujemy jako parę numerów miast połączonych przez tę drogę. Jako pierwsze należy wymienić miasto o mniejszym numerze. Numery miast należy oddzielić pojedynczym odstępem.
Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać jedno, dowolne z nich.
Dla danych wejściowych:
11 13 5 1 2 1 3 1 5 3 5 2 8 4 11 7 11 6 10 6 9 2 3 8 9 5 9 9 10
jednym z poprawnych wyników jest:
3 2 3 5 9 3 5
Autor zadania: Marek Cygan.