Metro
Limit pamięci: 128 MB
W pewnym mieście od długiego czasu zmagano się z budową metra.
Przy tym źle gospodarowano środkami, nie doszacowano
kosztów budowy i zapomniano przewidzieć pieniądze na zakup
pociągów.
W rezultacie zbudowano wiele stacji, ale wydrążono tylko część
zaplanowanych tuneli - ledwie wystarczających do tego, żeby
pomiędzy każdymi dwiema stacjami istniała możliwość przejazdu.
Liczba tuneli jest o 1 mniejsza od liczby zbudowanych stacji,
ponadto wszystkie tunele są dwukierunkowe.
Za pozostałe środki udało się kupić zaledwie kilka pociągów.
Chcąc ratować twarz, dyrekcja metra zwróciła się do Ciebie z
prośbą o opracowanie tras pociągów w taki sposób, by możliwie
najwięcej stacji znalazło się na trasach linii metra.
Każdy pociąg musi jeździć po ustalonej trasie.
Trasy muszą być proste, tzn. nie mogą się rozgałęziać
(żadne trzy tunele zbiegające się na jednej stacji nie mogą
jednocześnie leżeć na tej samej trasie).
Kilka tras może natomiast przebiegać przez tę samą stację lub
ten sam tunel.
Zadanie
Zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia opis sieci tuneli
oraz liczbę tras pociągów metra, które należy zaplanować
-
obliczy maksymalną liczbę stacji, jakie mogą się znaleźć
na wymaganej liczbie tras metra,
-
zapisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia zapisane są dwie liczby całkowite
i (, )
oddzielone pojedynczym odstępem.
Liczba to liczba stacji, a to liczba tras pociągów,
które należy zaplanować.
Stacje są ponumerowane od 1 do .
W każdym z kolejnych wierszy znajdują się po dwie różne
liczby całkowite oddzielone pojedynczym odstępem.
Liczby znajdujące się w -szym
wierszu są numerami stacji połączonych przez -ty tunel.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy zapisać
jedną liczbę całkowitą równa maksymalnej liczbie stacji,
jakie mogą znaleźć się na trasach pociągów.
Przykład
Dla danych wejściowych:
17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10
poprawną odpowiedzią jest:
13
Na rysunku przedstawiono sieć tuneli z zaznaczonymi trasami
metra w jednym z optymalnych układów.
Autor zadania: Karol Cwalina.