Paliwo [B]
Limit pamięci: 128 MB
W Bajtocji jest miast, które dawniej były połączone gęstą siecią dwukierunkowych dróg.
Każda droga łączyła dwa różne miasta.
Mieszkańcy z sentymentem wracają myślami do tamtych dni, bowiem pewnego dnia król Bajtocji postanowił
ograniczyć liczbę dróg w kraju i zwrócił się do nadwornego informatyka z prośbą o pomoc.
Teraz w Bajtocji jest więc zaledwie dróg, a z każdego miasta do każdego innego da się dojechać dokładnie jedną trasą.
Bajtazar ma zatankowany samochód, który umożliwia mu przejechanie dokładnie odcinków dróg pomiędzy miastami.
Teraz chciałby odwiedzić jak najwięcej różnych miast, jednak nie wie, którymi trasami powinien pojechać.
Pomóż mu i powiedz, ile różnych miast może odwiedzić, jeśli może rozpocząć podróż w dowolnym mieście
(sobie znanym sposobem zamierza się tam dostać, nie zużywając paliwa) i zakończyć również w dowolnym mieście.
Bajtazar może jeździć jedną drogą wielokrotnie.
Wejście
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz (), oznaczające
odpowiednio liczbę miast w Bajtocji oraz maksymalną liczbę dróg, jakie Bajtazar może przejechać samochodem bez
dodatkowych tankowań.
Miasta są ponumerowane od do .
W kolejnych wierszach jest opisana sieć dróg.
W każdym z tych wierszy znajdują się dwie liczby całkowite , () oznaczające, że
pomiędzy miastami i prowadzi dwukierunkowa droga.
Wszystkie drogi mają jednakową długość.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą maksymalnej liczbie różnych miast, które może odwiedzić Bajtazar.
Przykład
Dla danych wejściowych:
7 6
1 2
2 3
2 5
5 6
5 7
4 5
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu: Bajtazar może odwiedzić 5 różnych miast, korzystając np. z trasy
lub z trasy
.
Autor zadania: Jacek Tomasiewicz.