题目背景

某市新建的轨道交通网络由 $2n$ 条地铁线路构成,组成 $n$ 纵 $n$ 横的交通网。每条线路包含 $n$ 个车站,每个车站位于一组纵横线路的交汇处。

题目描述

由于建设成本的限制,并非每个车站都能进行站内换乘。能够换乘的车站共有 $m$ 个。

已知地铁运行 $1$ 站需要 $2$ 分钟,站内换乘需要步行 $1$ 分钟。小明想知道,在不中途出站的前提下,从学校到家最快需要多少时间（等车时间忽略不计）。

注意：学校和家所在的车站一定可以直接上车和下车,不需要换乘。

输入格式

第一行有两个整数 $n, m$。

接下来 $m$ 行,每行两个整数 $x, y$,表示第 $x$ 条横向线路与第 $y$ 条纵向线路的交汇站是换乘站。

最后一行四个整数 $x_1, y_1, x_2, y_2$,表示小明从学校出发时在第 $x_1$ 条横向线路与第 $y_1$ 条纵向线路的交汇站上车,到家时在第 $x_2$ 条横向线路与第 $y_2$ 条纵向线路的交汇站下车。

输出格式

输出一个整数,表示小明从学校到家的最短时间。如果无法到达,输出 $-1$。

样例

2 1
1 2
1 1 2 2

5

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

27

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

26

提示

对于 $30\%$ 的数据, $n \le 50, m \le 1000$；

对于 $60\%$ 的数据, $n \le 500, m \le 2000$；

对于 $100\%$ 的数据, $n \le 20000, m \le 100000$。