#P5683. [CSP-J2019 江西] 道路拆除

[CSP-J2019 江西] 道路拆除

题目描述

A 国有 nn 座城市,从 1n1 \sim n 编号。11 号城市是 A 国的首都。城市间由 mm 条双向道路连通,通过每一条道路所花费的时间均为 11 单位时间。

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

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

输入格式

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

接下来 mm 行,每行两个正整数 x,yx,y,表示一条连接 xx 号点与 yy 号点的道路。数据保证没有重边和自环。

最后一行四个整数,分别为 s1,t1,s2,t2s_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%30\% 的数据,n,m15n,m \le 15
另有 20%20\% 的数据,n100n \le 100m=n1m = n-1
另有 30%30\% 的数据,s1=s2s_1 = s_2
对于 100100% 的数据,2n,m30002 \le n,m \le 30001x,yn1\le x,y \le n2s1,s2n2 \le s_1,s_2 \le n0t1,t2n0 \le t_1,t_2 \le n

【样例 11 解释】
拆除 (1,2),(2,3),(3,4)(1,2),(2,3),(3,4) 三条边。
注意:不需要令首都与除了 s1,s2s_1,s_2 外的点在拆除之后依然连通。

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

testdata by @DYH060310