Description

Country A has $n$ cities, numbered from $1 \sim n$. City $1$ is the capital of Country A. The cities are connected by $m$ undirected roads, and the time to travel along each road is $1$ unit of time.

Now Country A plans to remove some impractical roads to reduce maintenance costs, but it also needs to ensure that the main routes are not affected. Therefore, after the road removals, using the remaining roads, starting from the capital of Country A, it must be possible to reach city $s_1$ and city $s_2$, and the shortest times required must be no more than $t_1$ and $t_2$, respectively (note that these are two independent conditions with no relation to each other; that is, you do not need to go to $s_1$ first and then to $s_2$).

Country A asks you to compute, under the above conditions, the maximum number of roads that can be removed. If the above conditions can never be satisfied, output $-1$.

Input Format

The first line contains two positive integers $n, m$, representing the number of cities and the number of roads.

The next $m$ lines each contain two positive integers $x, y$, representing a road connecting node $x$ and node $y$.

The last line contains four integers, which are $s_1, t_1, s_2, t_2$.

Output Format

Only one line containing one integer, representing the answer.

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

Hint

Constraints
For $30\%$ of the testdata, $n, m \le 15$.
For another $20\%$ of the testdata, $n \le 100$ and $m = n - 1$.
For another $30\%$ of the testdata, $s_1 = s_2$.
For $100\%$ of the testdata, $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$.

Explanation of Sample $1$
Remove three edges: $(1,2)$, $(2,3)$, $(3,4)$.
Note: It is not necessary to keep the capital connected to nodes other than $s_1, s_2$ after the removal.

Explanation of Sample $2$
Even if not a single edge is removed, the shortest time from the capital to node $3$ is already $2$ units of time.

testdata by @DYH060310

Translated by ChatGPT 5