← 返回题目列表

Codeforces · 543/B

B. 毁坏道路

中文机器翻译题面 查看原题

在某个国家,恰好有 n 个城市和 m 条连接城市的双向道路。城市用 1 到 n 的整数进行编号。如果a和b城市有一条路相连,那么一个小时内,你可以沿着这条路从a城市到b城市,或者从b城市到a城市。道路网络是这样的,从任何一个城市,你都可以沿着道路到达任何另一个城市。

您想要摧毁该国尽可能多的道路,以便剩余的道路可以让您在最多 l1 小时内从城市 s1 到达城市 t1,​​并在最多 l2 小时内从城市 s2 到达城市 t2。

确定为了满足计划条件而需要破坏的最大道路数量。如果无法达到期望的结果,则打印-1。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 3000, $$n-1\leq m\leq \min\{3000,\frac{n(n-1)}{2}\}$$) — 分别是该国家/地区的城市和道路数量。

接下来的 m 行包含对道路的描述,作为整数对 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。保证描述中给出的道路可以将您从任何城市运送到任何其他城市。保证每对城市之间最多有一条道路。

最后两行各包含三个整数,分别为 s1、t1、l1 和 s2、t2、l2(1 ≤ si、ti ≤ n、0 ≤ li ≤ n)。

输出

打印一个数字——问题的答案。如果不可能满足条件,则打印-1。

示例

输入 #1

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

输出 #1

0

输入 #2

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

输出 #2

1

输入 #3

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

输出 #3

-1