Дороги

면접 대비

시간 제한2초메모리 제한1024 MB

요약

기존의 단위 격자 도로가 주어질 때, 시장 집 (mx, my)에서 시청 (0,0)까지 이어지도록 추가로 지어야 하는 최소 도로 수를 구한다.

난이도: 보통10점 중 5점
유형: 그래프, BFS, 최단 경로, 구현
정답자: 아직 제출이 없습니다

문제

Дорожная сеть города Нью-Флетсити устроена довольно просто. Все дороги являются отрезками единичной длины с концами в точках с целыми координатами. Этот факт --- своего рода достопримечательность Нью-Флетсити.

Недавно пришедший к власти мэр считает, что он тратит слишком много времени на дорогу из дома в мэрию и обратно. Он решил построить несколько новых дорог так, чтобы этот путь был как можно короче. Естественно, новые дороги должны также являться единичными отрезками с концами в целых точках.

Вам, как главному инженеру Нью-Флетсити, поручено вычислить минимальное количество дорог, которое придется построить для осуществления плана мэра.

입력

Первая строка входного файла содержит целое число $n$ --- количество дорог в Нью-Флетсити ( $0 \le n \le 100$ ). Далее следуют $n$ строк с четырьмя целыми числами, разделенными пробелами: $x\_i, y\_i, x\_j, y\_j$ --- координаты начала и конца соответствующей дороги ( $0 \le x\_i, y\_i, x\_j, y\_j \le 100$ ). Последняя строка содержит два целых числа $m\_x$ и $m\_y$ --- координаты дома мэра ( $0 \le m\_x, m\_y \le 100$ ). Мэрия расположена в точке $(0, 0)$ .

Все дороги расположены либо по горизонтали, либо по вертикали, а длина каждой из этих дорог равна единице. Движение по дорогам возможно в обе стороны.

출력

В выходной файл на первой строке выведите число $M$ --- количество новых дорог, которые нужно построить в Нью-Флетсити.

예제2

예제 1
입력
```
1
0 0 1 0
1 1
```
예상 출력
```
1
```

예제 2

입력

예상 출력