Destroying Roads

题面翻译

题目描述

在这个国家有$n$ 个城市，城市间由$m$ 条双向公路连接。城市被编号为$1$ 到$n$ 。如果城市$a$ 和$b$ 被公路连接，那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$ 小时。

你想要破坏最多的公路，但是破坏后必须满足从指定城市$s_1$ 到$t_1$ 最短不超过$l_1$ 小时，且从指定城市$s_2$ 到$t_2$ 最短不超过$l_2$ 小时。

计算在符合条件的情况下能破坏的最多公路数量。如果无论如何都无法满足条件，输出$-1$ 。

输入格式

第一行包含两个整数$n, m \ (1 \leq n \leq 3000, n - 1 \leq m \leq \min\{3000, \frac{n(n-1)}{2}\})$ ，分别代表城市的数量和公路的数量。

下面的$m$ 行包含描述公路的整数对$a_i, b_i \ (1 \leq a_i, b_i \leq n, a_i \neq b_i)$ 。数据保证没有重边。

最后的$2$ 行每行包含三个整数$s_1, t_1, l_1$ 和$s_2, t_2, l_2 \ (1 \leq s_i, t_i \leq n, 0 \leq l_i \leq n)$ 。

输出格式

输出一行一个整数，即问题的答案。如果无论如何都无法满足条件，输出$-1$ 。

感谢@KSkun 提供的翻译

题目描述

In some country there are exactly $n$ cities and $m$ bidirectional roads connecting the cities. Cities are numbered with integers from $1$ to $n$ . If cities $a$ and $b$ are connected by a road, then in an hour you can go along this road either from city $a$ to city $b$ , or from city $b$ to city $a$ . The road network is such that from any city you can get to any other one by moving along the roads.

You want to destroy the largest possible number of roads in the country so that the remaining roads would allow you to get from city $s_{1}$ to city $t_{1}$ in at most $l_{1}$ hours and get from city $s_{2}$ to city $t_{2}$ in at most $l_{2}$ hours.

Determine what maximum number of roads you need to destroy in order to meet the condition of your plan. If it is impossible to reach the desired result, print -1.

输入格式

The first line contains two integers $n$ , $m$ ( $1<=n<=3000$ , ) — the number of cities and roads in the country, respectively.

Next $m$ lines contain the descriptions of the roads as pairs of integers $a_{i}$ , $b_{i}$ ( $1<=a_{i},b_{i}<=n$ , $a_{i}≠b_{i}$ ). It is guaranteed that the roads that are given in the description can transport you from any city to any other one. It is guaranteed that each pair of cities has at most one road between them.

The last two lines contains three integers each, $s_{1}$ , $t_{1}$ , $l_{1}$ and $s_{2}$ , $t_{2}$ , $l_{2}$ , respectively ( $1<=s_{i},t_{i}<=n$ , $0<=l_{i}<=n$ ).

输出格式

Print a single number — the answer to the problem. If the it is impossible to meet the conditions, print -1.

样例 #1

样例输入 #1

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

样例输出 #1

0

样例 #2

样例输入 #2

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

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

-1