Tour de Bajtocja
Limit pamięci: 128 MB
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.
Wejście
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 .
Wyjście
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.
Przykład
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.