题目描述

译自 CEOI 2014 Day2 T1「007」，原网站因为神秘原因没法访问了，这里用的 Web Archive 链接。

007 特工发现了她最大的敌人 De Referenced Nullpointer 博士（简称 Dr. Null）的一个阴谋：Dr. Null 将要摧毁 LOJ 的两台服务器中的某一台！Dr. Null 正准备去实施他的方案，并且他也正在去服务器的路上。很遗憾，这意味着 007 必须告别她正在泡着帅哥吃早餐的生活。

007 和 Dr. Null 都入侵了一个卫星系统，所以他们总是知道对方的位置。卫星系统把地图表示为一个连通的无向图，007 和 Dr. Null 以及两台服务器都位于节点上。特别地，保证两台服务器位于相邻的两个节点上。007 和 Dr. Null 都可以在一个单位时间内移动一条边，不过也可以不移动。Dr. Null 摧毁服务器也需要一个单位时间。Dr. Null 和 007 轮流行动，Dr. Null 先手。

如果 007 抓住了 Dr. Null（他们位于同一个节点上）或者可以保证 Dr. Null 在无限长的时间内无法摧毁服务器，就算 007 获胜。

007 想要知道她现在能吃着早餐泡帅哥最迟到什么时候，以确保无论 Dr. Null 采取什么策略依然可以取得胜利。

请你帮助 007 编写一个程序，计算她为了确保胜利，最迟停下吃早餐的时间。注意：当 007 还在吃早餐的时候她是没有办法抓住 Dr. Null 的，即使他们位于同一个节点上也不行。

输入格式

第一行两个正整数 $n, m$，分别表示图中节点数和边数。
第二行四个互不相同的正整数 $s, d, a, b$，分别表示 007 的初始位置，Dr. Null 的初始位置，以及两台服务器的位置。
接下来 $m$ 行，每行两个正整数 $u, v$，表示一条连接节点 $u$ 和 $v$ 之间的边。

输出格式

输出一行一个数，表示为了确保胜利，007 最多还能吃多久的早餐。具体地说，如果 007 在一开始就必须行动则输出 $0$。
如果 007 无论如何都无法胜利，输出 $-1$。

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

1

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4

0

数据范围与提示

对于所有数据，保证 $4 \le n \le 2 \times {10}^5$，$3 \le m \le 6 \times {10}^5$，$1 \le s, d, a, b \le n$ 且互不相同，保证图连通。

部分分设置：对于每个子任务，如果你的程序的输出在其中至少一组测试点中比非负的正确答案少 $1$ 并且在其它测试点中完全正确，则你将获得该子任务的 $30 \%$ 的分数。注意如果正确答案是 $0$ 时你的程序输出 $-1$ 也算作这种情况。