La ley de Moore afirma que el número de transistores en un chip se duplica cada dos años. Sorprendentemente, esta ley se ha cumplido durante más de medio siglo. Cada vez que la tecnología existente impedía seguir creciendo, los investigadores ideaban nuevas tecnologías de fabricación para empaquetar circuitos con aún mayor densidad. En un futuro cercano, esto podría significar fabricar chips en tres dimensiones en lugar de dos. Pero para este problema bastarán dos dimensiones.

Un problema común a todo diseño de hardware bidimensional (por ejemplo, chips, tarjetas gráficas, placas base, etc.) es la colocación de cables. Al tender cables en el hardware, resulta problemático que tengan que cruzarse. Cuando hay un cruce, deben usarse dispositivos especiales para permitir que dos cables eléctricos pasen uno sobre otro, lo cual encarece la fabricación.

Nuestro problema es el siguiente: se te da un diseño de hardware con varios cables ya colocados (todos son segmentos de recta). También se te dan los puntos inicial y final de una nueva conexión por cable que debe añadirse. Debes determinar el número mínimo de cables existentes que hay que cruzar para conectar esos puntos. La conexión no tiene por qué ser una línea recta. El único requisito es que no puede cruzar en un punto donde dos o más cables ya se toquen o se intersequen.

Figura L.1: Primera entrada de ejemplo.

La figura L.1 muestra la primera entrada de ejemplo. Ocho cables existentes forman cinco cuadrados. Los puntos inicial y final de la nueva conexión están en los cuadrados de los extremos izquierdo y derecho, respectivamente. La línea negra discontinua muestra que una conexión directa cruzaría cuatro cables, mientras que la solución óptima solo cruza dos (la curva azul).

Entrada

La entrada consiste en un único caso de prueba. La primera línea contiene cinco enteros $m,x_0,y_0,x_1,y_1$, que son el número de cables existentes ($m \le 100$) y los puntos inicial y final que deben conectarse. A continuación hay $m$ líneas, cada una con cuatro enteros $x_a,y_a,x_b,y_b$ que describen un cable existente de longitud no nula desde $(x_a,y_a)$ hasta $(x_b,y_b)$. El valor absoluto de cada coordenada de entrada es menor que $10^5$. Cada par de cables tiene como máximo un punto en común; es decir, los cables no se solapan. Los puntos inicial y final del nuevo cable no se encuentran sobre ningún cable existente.

Salida

Muestra el número mínimo de cables que deben cruzarse para conectar los puntos inicial y final.

Ejemplos

Entrada 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

Salida 1

2

Entrada 2

1 0 5 10 5
0 0 10 10

Salida 2

0