#P5683. [CSP-J2019 江西] 道路拆除
[CSP-J2019 江西] 道路拆除
题目描述
A 国有 座城市,从 编号。 号城市是 A 国的首都。城市间由 条双向道路连通,通过每一条道路所花费的时间均为 单位时间。
现在 A 国打算拆除一些不实用的道路以减小维护的开支,但 A 国也需要保证主要线路不受影响。因此 A 国希望道路拆除完毕后,利用剩余未被拆除的道路,从 A 国首都出发,能到达 号与 号城市,且所要花费的最短时间分别不超过 与 (注意这是两个独立的条件,互相之间没有关联,即不需要先到 再到 )。
A 国想请你帮他们算算,在满足上述条件的情况下,他们最多能拆除多少条道路。 若上述条件永远无法满足,则输出 。
输入格式
第一行两个正整数 ,表示城市数与道路数。
接下来 行,每行两个正整数 ,表示一条连接 号点与 号点的道路。数据保证没有重边和自环。
最后一行四个整数,分别为 。
输出格式
仅一行一个整数,表示答案。
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
提示
【数据范围】
对于 的数据,;
另有 的数据,,;
另有 的数据,;
对于 的数据,,,,。
【样例 解释】
拆除 三条边。
注意:不需要令首都与除了 外的点在拆除之后依然连通。
【样例 解释】
即使一条边都不拆除,首都到 号点的最短时间也都达到了 单位时间。
testdata by @DYH060310