在某个国家,恰好有 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