Prawo Moore’a mówi, że liczba tranzystorów na chipie podwaja się co dwa lata. Co zadziwiające, prawo to sprawdza się od ponad pół wieku. Gdy dotychczasowa technologia nie pozwalała na dalszy wzrost, naukowcy opracowywali nowe technologie produkcji umożliwiające jeszcze gęstsze upakowanie obwodów. W niedalekiej przyszłości może to oznaczać budowanie chipów w trzech wymiarach zamiast w dwóch. W tym zadaniu wystarczą jednak dwa wymiary.

Problemem wspólnym dla wszystkich dwuwymiarowych projektów sprzętu (na przykład chipów, kart graficznych, płyt głównych itd.) jest rozmieszczenie przewodów. Przy prowadzeniu przewodów na sprzęcie problem pojawia się, gdy muszą się one krzyżować. W takim miejscu potrzebne są specjalne elementy pozwalające dwóm przewodom elektrycznym przejść jeden nad drugim, co podnosi koszty produkcji.

Nasze zadanie jest następujące: dany jest projekt sprzętu z kilkoma już umieszczonymi przewodami (wszystkie są odcinkami prostych). Dane są też punkt początkowy i końcowy nowego połączenia przewodowego. Należy wyznaczyć minimalną liczbę istniejących przewodów, które trzeba przeciąć, aby połączyć te punkty. Połączenie nie musi być linią prostą. Jedynym wymaganiem jest to, że nie wolno przecinać w punkcie, w którym co najmniej dwa istniejące przewody już się stykają lub przecinają.

Rysunek L.1: Pierwsze przykładowe wejście.

Rysunek L.1 przedstawia pierwsze przykładowe wejście. Osiem istniejących przewodów tworzy pięć kwadratów. Początek i koniec nowego połączenia znajdują się odpowiednio w skrajnie lewym i skrajnie prawym kwadracie. Czarna linia przerywana pokazuje, że bezpośrednie połączenie przecinałoby cztery przewody, natomiast rozwiązanie optymalne przecina tylko dwa (niebieska krzywa).

Wejście

Wejście zawiera jeden przypadek testowy. Pierwszy wiersz zawiera pięć liczb całkowitych $m,x_0,y_0,x_1,y_1$, określających liczbę istniejących przewodów ($m \le 100$) oraz początek i koniec wymaganego połączenia. Dalej następuje $m$ wierszy, każdy zawierający cztery liczby całkowite $x_a,y_a,x_b,y_b$ opisujące istniejący przewód niezerowej długości od $(x_a,y_a)$ do $(x_b,y_b)$. Wartość bezwzględna każdej współrzędnej na wejściu jest mniejsza niż $10^5$. Każda para przewodów ma co najwyżej jeden punkt wspólny, czyli przewody nie nakładają się na siebie. Początek i koniec nowego przewodu nie leżą na żadnym istniejącym przewodzie.

Wyjście

Wypisz minimalną liczbę przewodów, które należy przeciąć, aby połączyć punkt początkowy i końcowy.

Przykład

Wejście 1

8 3 3 19 3
0 1 22 1
0 5 22 5
1 0 1 6
5 0 5 6
9 0 9 6
13 0 13 6
17 0 17 6
21 0 21 6

Wyjście 1

2

Wejście 2

1 0 5 10 5
0 0 10 10

Wyjście 2

0