Problem Background

SHOI2012 D2T1

Problem Description

In the year 2046, the urban rail transit system in OI City has finally been completed. The constructed rail network consists of $2n$ subway lines, forming an $n$ by $n$ grid. As shown in the figure below, each of these $2n$ lines includes $n$ stations, and each station is located at the intersection of a horizontal and a vertical line.

Due to construction costs, not every station is equipped for in-station transfers. There are $m$ stations that allow for such transfers. In the figure, stations marked with a square icon are transfer stations. It is known that traveling one station takes 2 minutes, and an in-station transfer requires 1 minute of walking. Serenade wants to know the minimum time needed to get home from school without exiting the station (waiting time for the train is ignored).

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $x$ and $y$, indicating that the intersection of the $x$-th horizontal line and the $y$-th vertical line is a transfer station.

The next line contains four integers $x_1, y_1, x_2, y_2$. This indicates that Serenade boards at the intersection of the $x_1$-th horizontal line and the $y_1$-th vertical line, and disembarks at the intersection of the $x_2$-th horizontal line and the $y_2$-th vertical line.

Output Format

The output file contains a single line, which is the time Serenade needs to get home under the best route selection. If Serenade cannot get home without exiting the station, output -1.

Sample Input and Output

Sample Input #1

2 1
1 2
1 1 2 2

Sample Output #1

5

Sample Input #2

6 9
2 1
2 5
3 2
4 4
5 2
5 6
6 1
6 3
6 4
1 1 4 6

Sample Output #2

27

Sample Input #3

6 10
2 1
2 5
3 2
4 4
5 2
5 6
6 1
6 3
6 4
6 6
1 1 4 6

Sample Output #3

26

Notes

For 30% of the data, $n \le 50, m \le 1000$;

For 60% of the data, $n \le 500, m \le 2000$;

For 100% of the data, $n \le 20000, m \le 100000$.

见题面 Input 部分

见题面 Output 部分