Problem Description

Country A has $n$ cities numbered from $1$ to $n$. City $1$ is the capital of Country A. There are $m$ bidirectional roads connecting the cities, and it takes $1$ unit of time to travel on each road.

Country A plans to demolish some impractical roads to reduce maintenance costs, but they also need to ensure that the main routes are not affected. Therefore, after the demolition, Country A wants to ensure that using the remaining undemolished roads, it is possible to reach city $s_1$ and city $s_2$ from the capital, with the shortest travel times not exceeding $t_1$ and $t_2$ respectively (note that these are two independent conditions, and there is no requirement to go from $s_1$ to $s_2$).

Country A would like you to calculate the maximum number of roads they can demolish while satisfying the above conditions. If the conditions can never be met, output $-1$.

Input Format

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

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

The last line contains four integers: $s_1$, $t_1$, $s_2$, and $t_2$.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

3 2
1 2
2 3
2 2 3 1

Sample Output #2

-1

Notes

Data Range

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

Sample #1 Explanation

Demolish the roads $(1,2)$, $(2,3)$, and $(3,4)$.
Note: It is not necessary to keep the capital connected to other cities except $s_1$ and $s_2$ after demolition.

Sample #2 Explanation

Even if no roads are demolished, the shortest time from the capital to city $3$ is already $2$ units of time.

见题面 Input 部分

见题面 Output 部分