Prawoskrętny wielbłąd

Limit pamięci: 32 MB

Bajtocja składa się z oaz leżących na pustyni, przy czym żadne trzy oazy nie leżą na jednej linii prostej. Bajtazar mieszka w jednej z nich, a w każdej z pozostałych ma po jednym znajomym. Bajtazar chce odwiedzić jak najwięcej swoich znajomych. Zamierza pojechać na swoim wielbłądzie. Wielbłąd ten porusza się niestety w dosyć ograniczony sposób:

• Po wyjściu z oazy wielbłąd porusza się po linii prostej, aż dotrze do innej oazy.
• Wielbłąd skręca tylko w oazach, jednak tylko w prawo, o kąt z przedziału (wielbłąd może tylko raz obrócić się w oazie, tzn. nie jest dozwolony n.p. obrót o w wyniku dwóch kolejnych obrotów o ).
• Wielbłąd nie chce chodzić po własnych śladach.

Pomóż Bajtazarowi tak ustalić trasę podróży, aby odwiedził jak najwięcej znajomych. Powinna ona zaczynać i kończyć się w oazie, w której mieszka Bajtazar. Musi składać się z odcinków łączących kolejno odwiedzane oazy. Trasa ta nie może dwa razy przechodzić przez ten sam punkt, z wyjątkiem oazy Bajtazara, gdzie wielbłąd pojawia się dwukrotnie: na początku i na końcu trasy.

Początkowo wielbłąd Bajtazara jest już ustawiony w kierunku konkretnej oazy i musi wyruszyć w tym kierunku. Ustawienie wielbłąda po powrocie z podróży nie ma znaczenia.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia współrzędne oaz oraz ustawienie wielbłąda,
• obliczy maksymalną liczbę znajomych, których Bajtazar może odwiedzić zgodnie z powyższymi regułami,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisana jest jedna liczba całkowita () - liczba oaz w Bajtocji. Oazy są ponumerowane od do . Bajtazar mieszka w oazie nr , a jego wielbłąd stoi zwrócony w stronę oazy nr . W kolejnych wierszach umieszczone są współrzędne oaz. W -ym wierszu znajdują się dwie liczby całkowite , - pozioma i pionowa współrzędna -tej oazy - oddzielone pojedynczym odstępem. Wszystkie współrzędne są z zakresu od do .

Wyjście

W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać jedną liczbę całkowitą - największą liczbę znajomych, których może odwiedzić Bajtazar.

Przykład

Dla danych wejściowych:

6
1 1
-1 4
0 -1
4 1
0 3
1 4

poprawną odpowiedzią jest:

4

Autor zadania: Paweł Parys.