A 国有 n 座城市，从 1 \sim 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。

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

【数据范围】
对于 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 单位时间。