Teleporty
Limit pamięci: 64 MB
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ć.
Wejście
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.
Wyjście
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.
Przykład
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.