题目描述：

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

你想在乡间小路上摧毁最大可能的道路数量，使剩余的道路将允许您从城市s1到t1中最多用不超过l1小时，从城市s2到城市t2最多用不超过l2小时。

确定您需要破坏的最大道路数量。如果无法达到预期目标，则打印 -1。

输入格式

第一行包含两个整数n,m(1 ≤n≤ 3000,) — 分别是国家的城市和道路数量。

接下来的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