Roads

Interview

Time limit2sMemory limit1024 MB

Summary

Given unit roads on an integer grid, find the fewest new unit roads that make the mayor's home-to-city-hall trip as short as possible.

Level: Medium4 of 10
Topics: Shortest path, BFS, Graph
Solved: No attempts yet

Problem

The road network of New Flatsity is quite simple. Every road is a unit-length segment whose endpoints have integer coordinates. This is one of the city's well-known features.

The recently elected mayor thinks he spends too much time on the road between his home and the city hall. He decided to build several new roads so that this trip is as short as possible. The new roads must also be unit segments with integer endpoints.

As New Flatsity's chief engineer, you must compute the minimum number of roads that need to be built to carry out the mayor's plan.

Input

The first line contains an integer $n$ ( $0 \le n \le 100$ ), the number of roads in New Flatsity. Each of the next $n$ lines contains four integers $x_i, y_i, x_j, y_j$ separated by spaces, the coordinates of the start and end of a road ( $0 \le x_i, y_i, x_j, y_j \le 100$ ). The last line contains two integers $m_x$ and $m_y$ , the coordinates of the mayor's home ( $0 \le m_x, m_y \le 100$ ). The city hall is at $(0, 0)$ .

Every road is either horizontal or vertical, and each has length 1. Roads can be traveled in both directions.

Output

Print on the first line the number $M$ , the number of new roads that must be built in New Flatsity.

Examples2

Example 1
Input
```
1
0 0 1 0
1 1
```
Expected output
```
1
```

Example 2

Input

Expected output