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