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.