La loi de Moore affirme que le nombre de transistors sur une puce double tous les deux ans. Étonnamment, cette loi reste valable depuis plus d'un demi-siècle. Chaque fois que les technologies existantes ne permettaient plus d'augmenter ce nombre, les chercheurs inventaient de nouvelles techniques de fabrication pour disposer les circuits encore plus densément. Dans un avenir proche, cela pourrait signifier construire des puces en trois dimensions plutôt qu'en deux. Mais pour ce problème, deux dimensions suffiront.

Un problème commun à toute conception de matériel en deux dimensions (par exemple les puces, cartes graphiques, cartes mères, etc.) est le placement des fils. Lorsqu'on fait passer des fils sur le matériel, il est problématique qu'ils doivent se croiser. À un croisement, des dispositifs spéciaux sont nécessaires pour permettre à deux fils électriques de passer l'un au-dessus de l'autre, ce qui augmente le coût de fabrication.

Notre problème est le suivant : on vous donne une conception matérielle comportant plusieurs fils déjà placés (tous sont des segments de droite). On vous donne aussi les points de départ et d'arrivée d'une nouvelle connexion par fil à ajouter. Vous devez déterminer le nombre minimal de fils existants qu'il faut traverser pour relier ces points. Cette connexion n'a pas besoin d'être une ligne droite. La seule exigence est qu'elle ne peut pas traverser un point où au moins deux fils se rejoignent ou se coupent déjà.

Figure L.1 : Première entrée d'exemple.

La figure L.1 représente la première entrée d'exemple. Huit fils existants forment cinq carrés. Les points de départ et d'arrivée de la nouvelle connexion se trouvent respectivement dans les carrés tout à gauche et tout à droite. La ligne noire en pointillés montre qu'une connexion directe traverserait quatre fils, alors que la solution optimale n'en traverse que deux (la courbe bleue).

Entrée

L'entrée comporte un seul cas de test. La première ligne contient cinq entiers $m,x_0,y_0,x_1,y_1$, qui indiquent le nombre de fils existants ($m \le 100$) et les points de départ et d'arrivée à relier. Elle est suivie de $m$ lignes contenant chacune quatre entiers $x_a,y_a,x_b,y_b$ décrivant un fil existant de longueur non nulle allant de $(x_a,y_a)$ à $(x_b,y_b)$. La valeur absolue de chaque coordonnée d'entrée est inférieure à $10^5$. Chaque paire de fils a au plus un point commun : les fils ne se chevauchent donc pas. Les points de départ et d'arrivée du nouveau fil ne se trouvent sur aucun fil existant.

Sortie

Affichez le nombre minimal de fils à traverser pour relier les points de départ et d'arrivée.

Exemples

Entrée 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

Sortie 1

2

Entrée 2

1 0 5 10 5
0 0 10 10

Sortie 2

0