Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

OI13_MET - Metro

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.

Wejście

W pierwszym wierszu wejścia zapisane są dwie liczby całkowite n i l (2 ≤ n ≤ 106, 0 ≤ l ≤ n) oddzielone pojedynczym odstępem. Liczba n to liczba stacji, a l to liczba tras pociągów, które należy zaplanować. Stacje są ponumerowane od 1 do n.

W każdym z kolejnych  wierszy znajdują się po dwie różne liczby całkowite oddzielone pojedynczym odstępem. Liczby ai, bi (1 ≤ ai, bi ≤ n) znajdujące się w (i+1)-szym wierszu są numerami stacji połączonych przez i-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

Wejście:

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

Wyjście:

13

http://main.edu.pl/pl/images/OI13/metzad.gif

Na rysunku przedstawiono sieć tuneli z zaznaczonymi trasami metra w jednym z optymalnych układów.


Dodane przez:Rafal Nowak
Data dodania:2007-12-05
Limit czasu wykonania programu:1s-6s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:XIII Olimpiada Informatyczna
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.