题目内容

某港区有 $n$ 个停靠点，编号 $1\sim n$，以及 $m$ 条双向车道。每条车道连接两个不同的停靠点。输入保证没有自环，也没有连接同一对停靠点的重复车道。行驶过程中可以重复经过同一个停靠点，也可以重复走同一条车道。

甲、乙两台牵引车分别从停靠点 $S_a$、$S_b$ 开往目标停靠点 $T_a$、$T_b$。输入保证出发时两人位置不同。

若出发时甲已经在 $T_a$、乙已经在 $T_b$，用时为 $0$，不必再移动。

否则从第 $1$ 秒起，每一秒两台车都必须各沿一条车道开到相邻停靠点，不能留在原地。已经停在自己目标上的车，只要另一台还没同时到达，下一秒也必须继续开出该点。

设某一秒甲从 $u$ 开到 $x$、乙从 $v$ 开到 $y$。这一秒合法，当且仅当同时满足：

• $u$ 与 $x$ 之间、$v$ 与 $y$ 之间都有车道；
• $x\ne y$，即走完后两人不能站在同一个停靠点；
• $x\ne v$ 且 $y\ne u$，即不能开进对方这一秒出发的那个停靠点。

请计算最少多少秒，两台车能同时位于各自的目标停靠点。无法做到时输出 $-1$。

输入描述

第一行两个整数 $n$、$m$，表示停靠点数量和车道数量。

第二行四个整数 $S_a$、$T_a$、$S_b$、$T_b$，依次表示甲的起点、甲的终点、乙的起点、乙的终点。

接下来 $m$ 行，每行两个整数 $u$、$v$，表示一条连接 $u$ 与 $v$ 的双向车道。

约束

$2 \le n \le 100$

$0 \le m \le 500$

$1 \le S_a,T_a,S_b,T_b \le n$

$S_a \ne S_b$

$1 \le u,v \le n$，且 $u\ne v$

任意两条车道连接的停靠点对不相同

输出描述

输出一个整数，表示两台车同时到达各自目标的最少秒数。无法做到时输出 $-1$。

样例1

输入

4 5
1 2 2 1
1 2
1 3
1 4
2 3
2 4

输出

2

说明

甲要从 $1$ 到 $2$，乙要从 $2$ 到 $1$。两人一开始都不在自己的终点，答案不是 $0$。

$1$ 秒内同时到达，只有甲走 $1\to 2$、乙走 $2\to 1$。走完后甲在 $2$、乙在 $1$，位置不同，但甲开进了乙的出发点 $2$，乙开进了甲的出发点 $1$，不合法。因此 $1$ 秒做不到。两人也不能停在原地等对方先让路。

下面一种走法用时 $2$ 秒：

• 第 $1$ 秒，甲 $1\to 3$，乙 $2\to 4$。落点 $3$ 和 $4$ 不同；甲没有进入 $2$，乙没有进入 $1$。
• 第 $2$ 秒，甲 $3\to 2$，乙 $4\to 1$。落点 $2$ 和 $1$ 不同；甲没有进入 $4$，乙没有进入 $3$。甲到达 $2$，乙到达 $1$。

因此最少秒数是 $2$。

样例2

输入

4 3
1 3 2 4
1 2
2 3
3 4

输出

-1

说明

车道是 $1-2-3-4$。甲要从 $1$ 到 $3$，乙要从 $2$ 到 $4$。

甲在 $1$ 只有一条车道，每一秒只要甲还停在 $1$，下一步只能开到 $2$。而出发时乙就在 $2$，第 $1$ 秒乙必然从 $2$ 出发，甲这一步会开进乙的出发点。第 $1$ 秒没有合法走法，后面也无法开始。输出 $-1$。

若只禁止走完后站在同一点，第 $1$ 秒甲 $1\to 2$、乙 $2\to 3$，第 $2$ 秒甲 $2\to 3$、乙 $3\to 4$，会得到 $2$ 秒。这两步甲都开进了乙当秒的出发点，按本题规则不合法。