W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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 .
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.
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