Polish version    English version  
  Historia OI -> XIII OI 2005/2006 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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.

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.




Wersja do druku