You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

Y国想请你帮他们算算，在满足上述条件的情况下，他们最多能拆除多少条道路。 若上述条件永远无法满足，则输出 $-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

3 2
1 2
2 3
2 2 3 1

-1

提示

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