Nożyczki [B]

Limit pamięci: 128 MB

Bajtazar kupił nożyczki. Teraz chciałby je przetestować, dlatego chwycił leżący w pobliżu wielokąt i postanowił pociąć go na prostokąty. Stwierdził, że zrobi to tak, aby wykonać jak najmniejszą liczbę cięć. Pomóż Bajtazarowi i oblicz, ile cięć będzie musiał wykonać.

Wielokąt składa się jedynie z pionowych i poziomych odcinków. Przed wzięciem nożyczek do ręki Bajtazar rysuje na wielokącie pewną liczbę pionowych i poziomych odcinków. Początek i koniec każdego odcinka leżą na brzegu wielokąta, zaś wnętrze odcinka zawiera się we wnętrzu wielokąta. Następnie Bajtazar przecina wielokąt wzdłuż wszystkich narysowanych odcinków. Liczba wykonanych cięć to liczba narysowanych odcinków. Po wykonaniu wszystkich cięć, wszystkie powstałe kawałki powinny mieć kształt prostokątów.

Zwróć uwagę, że po wykonaniu pewnej liczby cięć niektóre z narysowanych odcinków mogły zostać przecięte, jednak wykonanie cięć wzdłuż wszystkich kawałków powstałych z jednego narysowanego odcinka uznajemy za jedno cięcie. W szczególności oznacza to, że kwadrat o rozmiarze można podzielić na cztery kwadraty rozmiaru za pomocą zaledwie dwóch cięć (choć oczywiście z punktu widzenia celu, jaki postawił przed sobą Bajtazar, takie przecinanie nie ma sensu).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę wierzchołków wielokąta. Następne wierszy opisuje kolejne wierzchołki wielokąta. Opis -tego wierzchołka składa się z pary liczb całkowitych (), które opisują współrzędne tegoż wierzchołka.

Wszystkie boki wielokąta są pionowe lub poziome. Dwa boki wielokąta przecinają się jedynie wtedy, gdy są kolejnymi bokami na brzegu wielokąta. W takiej sytuacji ich jedynym punktem przecięcia jest wspólny wierzchołek. W szczególności współrzędne wszystkich wierzchołków są parami różne.

Wyjście

Twój program powinien wypisać na wyjście minimalną liczbę cięć potrzebną do podzielenia wielokąta na prostokąty.

Przykład

Dla danych wejściowych:

8
0 0
6 0
6 7
4 7
4 3
2 3
2 5
0 5

poprawną odpowiedzią jest:

2

Rysunek przedstawia kilka możliwych sposobów podziału wielokąta opisanego w przykładzie na prostokąty za pomocą dwóch cięć.

Autor zadania: Jakub Łącki.