A lei de Moore afirma que o número de transístores num chip duplica a cada dois anos. Surpreendentemente, esta lei tem-se mantido válida durante mais de meio século. Sempre que a tecnologia existente impedia um crescimento maior, os investigadores criavam novas tecnologias de fabrico para dispor circuitos com ainda mais densidade. Num futuro próximo, isso poderá significar construir chips em três dimensões em vez de duas. Mas, para este problema, duas dimensões bastam.

Um problema comum a todo o projeto de hardware bidimensional (por exemplo, chips, placas gráficas, placas-mãe, etc.) é a colocação dos fios. Ao encaminhar fios no hardware, é problemático terem de se cruzar. Quando ocorre um cruzamento, são necessários dispositivos especiais para permitir que dois fios elétricos passem um por cima do outro, o que encarece o fabrico.

O nosso problema é o seguinte: é dado um projeto de hardware com vários fios já colocados (todos segmentos de reta). Também são dados os pontos inicial e final de uma nova ligação por fio a acrescentar. É necessário determinar o número mínimo de fios existentes que têm de ser atravessados para ligar esses pontos. Esta ligação não precisa de ser uma linha reta. O único requisito é que não pode atravessar num ponto onde dois ou mais fios já se encontram ou se intersetam.

Figura L.1: Primeira entrada de exemplo.

A Figura L.1 mostra a primeira entrada de exemplo. Oito fios existentes formam cinco quadrados. Os pontos inicial e final da nova ligação encontram-se, respetivamente, nos quadrados mais à esquerda e mais à direita. A linha preta tracejada mostra que uma ligação direta atravessaria quatro fios, enquanto a solução ótima atravessa apenas dois (a curva azul).

Entrada

A entrada consiste num único caso de teste. A primeira linha contém cinco inteiros $m,x_0,y_0,x_1,y_1$, que indicam o número de fios existentes ($m \le 100$) e os pontos inicial e final a ligar. Seguem-se $m$ linhas, cada uma contendo quatro inteiros $x_a,y_a,x_b,y_b$ que descrevem um fio existente de comprimento não nulo de $(x_a,y_a)$ a $(x_b,y_b)$. O valor absoluto de cada coordenada de entrada é inferior a $10^5$. Cada par de fios tem no máximo um ponto em comum, ou seja, os fios não se sobrepõem. Os pontos inicial e final do novo fio não estão sobre nenhum fio existente.

Saída

Apresente o número mínimo de fios que têm de ser atravessados para ligar os pontos inicial e final.

Exemplos

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

Saída 1

2

Entrada 2

1 0 5 10 5
0 0 10 10

Saída 2

0