In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.