Fotoradary

Limit pamięci: 256 MB

Burmistrz Bajtogrodu zamierza postawić w mieście fotoradary. W Bajtogrodzie jest skrzyżowań, ponumerowanych liczbami od 1 do , oraz dwukierunkowych odcinków dróg. Każdy z tych odcinków łączy dwa skrzyżowania. Sieć dróg umożliwia dotarcie z każdego skrzyżowania do dowolnego innego.

Fotoradary mają być umieszczane na skrzyżowaniach (na każdym co najwyżej jeden), przy czym burmistrz chciałby postawić ich jak najwięcej. Aby nie denerwować zbytnio bajtogrodzkich kierowców, przyjął on, że na każdej trasie, która przebiega po drogach Bajtogrodu i nie odwiedza wielokrotnie żadnego skrzyżowania, może stać co najwyżej fotoradarów (włączając skrzyżowania na końcach trasy). Twoim zadaniem jest napisanie programu, który wyznaczy, gdzie należy postawić fotoradary.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (), oznaczające liczbę skrzyżowań w Bajtogrodzie i maksymalną liczbę fotoradarów, które mogą znaleźć się na pojedynczej trasie. Kolejne wierszy opisuje sieć dróg Bajtogrodu: w -tym z tych wierszy znajdują się dwie liczby całkowite i (), oznaczające, że istnieje dwukierunkowy odcinek drogi łączący skrzyżowania o numerach oraz .

Wyjście

W pierwszym wierszu wyjścia należy wypisać liczbę oznaczającą maksymalną liczbę fotoradarów, które można ustawić w Bajtogrodzie. W drugim wierszu należy wypisać ciąg liczb, będących numerami skrzyżowań, na których należy ustawić fotoradary. Jeśli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

5 2
1 3
2 3
3 4
4 5

jednym z poprawnych wyników jest:

3
1 2 4

Autor zadania: Tomasz Idziaszek