[CSP-J2019 江西] 道路拆除

题目描述

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$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3

输入样例 #2

3 2
1 2
2 3
2 2 3 1

输出样例 #2

-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$ 单位时间。 testdata by @DYH060310