CF543B.Destroying Roads

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.

在某个国家中，恰好有 $n$ 座城市和 $m$ 条双向道路连接这些城市。城市编号为 $1$ 到 $n$ 的整数。若城市 $a$ 与城市 $b$ 由一条道路相连，则你可以在一小时内沿该道路从城市 $a$ 到达城市 $b$，或从城市 $b$ 到达城市 $a$。该道路网络满足：从任意一座城市出发，均可通过道路到达其他任意一座城市。

你希望摧毁尽可能多的道路，使得剩余的道路仍能满足以下条件：

• 从城市 $s_1$ 到城市 $t_1$ 的行程耗时至多为 $l_1$ 小时；
• 从城市 $s_2$ 到城市 $t_2$ 的行程耗时至多为 $l_2$ 小时。

请确定为满足上述计划所需摧毁的道路的最大数量。若无法达成目标，请输出 $-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).

第一行包含两个整数 $n$、$m$（$1 ≤ n ≤ 3000$，），分别表示该国的城市数量和道路数量。

接下来的 $m$ 行每行描述一条道路，以一对整数 $a_i$、$b_i$ 给出（$1 ≤ a_i,\,b_i ≤ n$，且 $a_i ≠ b_i$）。题目保证所给道路构成的图中，任意两座城市之间均可互相到达。同时保证任意两座城市之间至多只有一条道路相连。

最后两行每行各包含三个整数：$s_1$、$t_1$、$l_1$ 和 $s_2$、$t_2$、$l_2$（其中 $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。