W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Król Bajtazar włada całym układem słonecznym, w którym znajduje się planet. Planety te są ponumerowane od 1 do . Jego pałac znajduje się na planecie nr 1, zaś jego baza wojskowa na planecie nr 2. Dawno temu Bajtazar wybudował teleport, który w ciągu dwustu pięćdziesięciu minut (czyli nieco ponad czterech godzin) jest w stanie przenieść go z planety nr 1 na planetę nr 2 lub z powrotem.
Obecnie dostępna jest bardziej zaawansowana technologia, która umożliwia tworzenie teleportów zapewniających transport między dwiema planetami w czasie jednej godziny (teleporty takie są z natury dwukierunkowe). Niektóre planety układu są już połączone takimi teleportami. Teleporty te umożliwiają przebycie trasy pomiędzy planetami 1 i 2, na szczęście nie szybciej niż prywatny teleport Bajtazara (co oczywiście zagrażałoby jego bezpieczeństwu).
Obecnie każda para planet, która nie jest jeszcze bezpośrednio połączona teleportem nowej generacji, złożyła wniosek o utworzenie łączącego ich takiego teleportu. Bajtazar chce się zgodzić na jak największą liczbę takich wniosków, ale tak, aby ciągle nie dało się pokonać trasy z planety nr 1 do 2 szybciej niż przy pomocy jego prywatnego teleportu. Pomóż mu określić, na ile nowych teleportów może się zgodzić.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę planet w królestwie Bajtazara oraz liczbę istniejących teleportów nowej generacji. W kolejnych wierszach opisane są już istniejące teleporty. W każdym z tych wierszy znajdują się po dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające, że istnieje teleport łączący planety i . Każda para liczb występuje na wejściu co najwyżej raz. Możesz założyć, że istniejące teleporty umożliwiają przedostanie się z planety nr 1 na planetę nr 2, ale nie w czasie krótszym niż 250 minut.
Twój program powinien wypisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitą, oznaczającą maksymalną liczbę nowych teleportów, na utworzenie których może zgodzić się Bajtazar.
Dla danych wejściowych:
10 10 1 3 3 5 5 7 7 9 2 9 1 4 4 6 6 8 8 10 2 10
poprawną odpowiedzią jest:
10
Linią ciągłą na rysunku zaznaczono istniejące teleporty, a przerywaną te, na budowę których Bajtazar może pozwolić.
Autor zadania: Jakub Onufry Wojtaszczyk.