Wielokąt
Limit pamięci: 32 MB
Dany jest -kąt wypukły (gdzie ) i jego różnych przekątnych, parami nie
przecinających się wewnątrz wielokąta. (Jedynym wspólnym punktem dwóch różnych
przekątnych może być tylko wierzchołek wielokąta.) Wierzchołki wielokąta są
ponumerowane kolejno od do w kierunku przeciwnym do
ruchu wskazówek zegara. Wszystkie przekątne dzielą na mniejsze
wielokąty wypukłe o rozłącznych wnętrzach.
Przykład
Cztery przekątne 1-8, 8-3, 3-1 i 3-6 dzielą wielokąt przedstawiony
na poniższym rysunku na dwa czworokąty i trzy trójkąty.
Zadanie
Ułóż program, który:
- wczytuje opis wielokąta i jego przekątnych ze standardowego
wejścia;
- oblicza maksymalną liczbę boków wielokąta wśród wielokątów wypukłych
powstałych z podziału ;
- zapisuje wynik w standardowym wyjściu.
Wejście
W każdym wierszu standardowego wejścia są zapisane dwie liczby całkowite
dodatnie oddzielone pojedynczym odstępem.
W pierwszym wierszu jest zapisana liczba wierzchołków wielokąta i
liczba przekątnych .
W każdym z kolejnych wierszy znajduje się opis jednej przekątnej
wielokąta w postaci pary liczb całkowitych dodatnich - numerów wierzchołków,
które łączy ta przekątna; bezpośrednio po drugiej z liczb następuje koniec
wiersza.
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego
sprawdzać.
Wyjście
W standardowym wyjściu należy zapisać jedną liczbę całkowitą dodatnią -
maksymalną liczbę boków wielokąta wypukłego powstałego z podziału danego
wielokąta .
Przykład
Dla danych wejściowych:
9 4
1 8
8 3
3 1
3 6
poprawną odpowiedzią jest:
4
Autor zadania: Krzysztof Diks.