#3289. 「CEOI2014」007

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: PinkRabbit

题目描述

译自 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

样例

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

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 n \le 300 m \le 1600
2 70 无特殊限制

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