#P6543. [CEOI2014] 007

[CEOI2014] 007

题目背景

CEOI2014 Day2 T1,译者:小粉兔

题目描述

007 特工发现了她最大的敌人 De Referenced Nullpointer 博士(简称 Dr. Null)的一个阴谋:Dr. Null 将要摧毁洛谷的两台服务器中的某一台!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,mn, m,分别表示图中节点数和边数。
第二行四个互不相同的正整数 s,d,a,bs, d, a, b,分别表示 007 的初始位置,Dr. Null 的初始位置,以及两台服务器的位置。
接下来 mm 行,每行两个正整数 u,vu, v,表示一条连接节点 uuvv 之间的边。

输出格式

输出一行一个数,表示为了确保胜利,007 最多还能吃多久的早餐。具体地说,如果 007 在一开始就必须行动则输出 00
如果 007 无论如何都无法胜利,输出 1-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

提示

对于所有数据,保证 4n2×1054 \le n \le 2 \times {10}^53m6×1053 \le m \le 6 \times {10}^51s,d,a,bn1 \le s, d, a, b \le n 且互不相同,保证图连通。

子任务编号 分值 特殊限制
11 3030 n300n \le 300m1600m \le 1600
22 7070 无特殊限制

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