In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
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ść.
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.
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.