题目描述

A 国有 n座城市，从 1∼n编号。1号城市是 A 国的首都。城市间由 m条双向道路连通，通过每一条道路所花费的时间均为 1单位时间。

现在 A 国打算拆除一些不实用的道路以减小维护的开支，但 A 国也需要保证主要线路不受影响。因此 A 国希望道路拆除完毕后，利用剩余未被拆除的道路，从 A 国首都出发，能到达 $s_{1}$号与 $s_{2}$号城市，且所要花费的最短时间分别不超过 $t_{1}$与 $t_{2}$（注意这是两个独立的条件，互相之间没有关联，即不需要先到 $s_{1}$再到 $s_{2}$）。

A 国想请你帮他们算算，在满足上述条件的情况下，他们最多能拆除多少条道路。 若上述条件永远无法满足，则输出 −1。

输入格式

第一行两个正整数 n,m，表示城市数与道路数。

接下来 m行，每行两个正整数 x,y，表示一条连接 x号点与 y号点的道路。

最后一行四个整数，分别为 $s_{1}$,$t_{1}$,$s_{2}$,$t_{2}$。

输出格式

仅一行一个整数，表示答案。

样例输入

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

样例输出

3

提示

说明与提示

数据范围

对于 30%的数据，$n,m\le 15$； 另有 20%的数据，$n\le 100$，$m=n-1$； 另有 30%的数据，$s_{1}=s_{2}$； 对于 100%的数据，$2\le n,m\le 3000$，$1\le x,y\le n$，$2\le s_{1},s_{2}\le n$，$0\le t_{1},t_{2}\le n$。

【样例 1解释】 拆除 (1,2),(2,3),(3,4)三条边。 注意：不需要令首都与除了 $s_{1}$,$s_{2}$外的点在拆除之后依然连通。

【样例 2解释】 即使一条边都不拆除，首都到 3号点的最短时间也都达到了 2单位时间。

3 2
1 2
2 3
2 2 3 1

-1

3 2 
1 2 
2 3 
2 2 3 1

-1

3 2  
1 2  
2 3  
2 2 3 1

-1