Plan remontów [A]
Limit pamięci: 64 MB
Bajtowa Góra rozpoczęła ostatnio program remontu dróg.
Rozpoczęcie prac utrudniło ruch w mieście, doszło do zamknięcia kilku ulic.
W ratuszu krążą słuchy, że dojazd do niektórych fragmentów miasta został
odcięty, jednak brak koordynatora remontów uniemożliwia rzetelne sprawdzenie tych doniesień.
Aby zapanować nad sytuacją, burmistrz Bajtowej Góry powołał Bajtazara na stanowisko
Miejskiego Informatyka do Spraw Koordynacji Inwestycji Drogowych.
Co prawda rozpoczętych już remontów nie można przerwać w połowie, jednakże
w budżecie remontowym wciąż pozostały fundusze ze ścisłym terminem wykorzystania.
Z tego względu burmistrz powierzył Bajtazarowi zadanie wyznaczenia listy ulic, które
mogą zostać dodatkowo zamknięte (jednocześnie) bez dalszego ograniczania możliwości poruszania się po mieście.
Dokładniej mówiąc, jeśli obecnie da się przejechać między pewną parą skrzyżowań w mieście, to po
zamknięciu ulic z listy Bajtazara również powinno to być możliwe.
Bajtazar z początku chciał znaleźć możliwie najliczniejszą listę, jednak nie uporał się z tym wyzwaniem.
Postanowił więc wyznaczyć taki zbiór ulic, do którego nie można dodać ani jednej ulicy, tak by nie odciąć
przejazdu pomiędzy żadną parą skrzyżowań, między którymi przejazd jest obecnie możliwy.
Napisz program, który pomoże Bajtazarowi wyznaczyć ulice do remontu.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz
(, ), określające liczbę skrzyżowań w mieście oraz liczbę jednokierunkowych ulic między nimi.
Skrzyżowania są ponumerowane od do .
Kolejne wierszy zawiera opisy poszczególnych ulic, w -tym spośród nich znajduje się opis
-tej ulicy w postaci pary liczb całkowitych , (, ).
Para taka oznacza, że istnieje ulica jednokierunkowa od skrzyżowania do skrzyżowania .
Każda uporządkowana para będzie wymieniona co najwyżej jednokrotnie.
Ponieważ remonty w mieście rozpoczęły się bez należytego przygotowania, nie należy zakładać niczego o obecnym kształcie sieci drogowej.
Wyjście
W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę
całkowitą , oznaczającą liczbę ulic na liście Bajtazara.
Kolejne wierszy powinno zawierać numery ulic do zamknięcia.
Ulice ponumerowane są od do , zgodnie z kolejnością występowania na wejściu.
Jeśli istnieje więcej niż jedna poprawna odpowiedź, należy wypisać jakąkolwiek z nich.
Przykład
Dla danych wejściowych:
5 6
1 2
1 3
2 3
3 2
2 4
3 4
poprawną odpowiedzią jest:
2
2
6
Autor zadania: Jakub Łącki.