Wyspy

Limit pamięci: 32 MB

Bajtocja jest oblana oceanem. Na jej terenie znajdują się jeziora. Na tych jeziorach wyspy, na tych wyspach zdarzają się dalsze jeziorka, a na nich wysepki i tak dalej. Ocean ma stopień zero. Bajtocja, jako wyspa ma stopień 1. Jeziora na wyspach Bajtocji stopień 2, itd., czyli jezioro ma stopień , jeśli znajduje się na wyspie stopnia , a wyspa ma stopień , jeśli znajduje się na jeziorze stopnia . Wynika stąd oczywiście, że wszystkie stopnie wysp są nieparzyste, a jezior i oceanu parzyste.

Wszystkie jeziora i wyspy mają linie brzegowe w kształcie wielokątów o prostopadłych kolejnych bokach (równoległych do osi układu współrzędnych), a ich wierzchołki mają współrzędne całkowite. Żadne dwie linie brzegowe nie przecinają się, ani nie stykają się.

Mając dane kontury linii brzegowych, wyznacz maksymalny stopień wyspy/jeziora w Bajtocji.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy linii brzegowych wysp i jezior,
• obliczy maksymalny stopień jeziora/wyspy,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisana jest jedna dodatnia liczba całkowita , liczba linii brzegowych, . Linie brzegowe są opisane w kolejnych wierszach, po jednej w wierszu. Każdy z tych wierszy zawiera nieujemne liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza liczba w wierszu to , parzysta liczba punktów tworzących linię brzegową, . Dalej w wierszu znajduje się liczb: , . Kolejne punkty tworzące linię brzegową to: , , , , ..., , . Są podane we współrzędnych kartezjańskich oraz opisują linię brzegową lewoskrętnie (czyli idąc z punktu do , wnętrze mamy po lewej stronie). Linie brzegowe są podane w takiej kolejności, że:

• linia brzegowa każdego jeziora jest podana zawsze po linii brzegowej wyspy, na której się znajduje,
• linia brzegowa każdej wyspy jest podana zawsze po linii brzegowej jeziora, na którym się znajduje.

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą: maksymalny stopień jeziora/wyspy.

Przykład

Dla danych wejściowych:

6
4 1 0 17 12
16 10 4 16 11 2 4 8 2 3 3 2 1 16 3 15 2
8 8 10 3 5 12 8 11 6
4 4 6 7 9
4 6 8 5 7
6 10 9 15 10 9 7

poprawną odpowiedzią jest:

5

Autor zadania: Piotr Chrząstowski.