Maximize Road Removal in A Country

A country A has n cities numbered from 1 to n with city 1 as its capital. There are m bidirectional roads connecting these cities, and traversing any road takes exactly 1 unit of time. Due to high maintenance costs, the government wants to remove as many roads as possible, but it must still be possible to start from the capital and reach city s₁ in no more than t₁ time units and city s₂ in no more than t₂ time units. Note that these two conditions are independent: the route to s₁ is not required to pass through s₂ or vice versa.

Your task is to calculate the maximum number of roads that can be removed such that these conditions are still satisfied. If it is impossible to satisfy the conditions even by keeping all roads, output \(-1\).

One way to view the problem is to select two paths from the capital (city 1) to the two designated cities, ensuring that the path lengths do not exceed \(t_1\) and \(t_2\) respectively. These two paths are allowed to share a common segment; if they do, the shared roads only need to be maintained once. Let the minimal number of roads that have to be kept be ans so that both conditions are met. Then, the answer will be \(m - ans\), i.e. the maximum number of roads that can be removed.

A common approach is to use breadth-first search (BFS) to compute shortest path distances from the capital, from s₁, and from s₂ to every other city. Using these distances, one can try all possible meeting points k (possibly including the capital) and check if it is possible to have:

• \(d(1, k) + d(k, s_1) \le t_1\)
• \(d(1, k) + d(k, s_2) \le t_2\)

Then, the required number of roads to be maintained would be \(d(1, k) + d(k, s_1) + d(k, s_2)\). Also, one must consider the possible case without any overlapping path (which is equivalent to taking \(k = 1\)).

inputFormat

The input starts with a line containing two integers \(n\) and \(m\) representing the number of cities and the number of roads. Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating there is a bidirectional road between cities \(u\) and \(v\). The final line contains four integers \(s_1\), \(t_1\), \(s_2\), and \(t_2\), where the conditions are that the shortest path from city 1 (the capital) to city \(s_1\) must have length at most \(t_1\) and to city \(s_2\) at most \(t_2\).

 n m
 u1 v1
 u2 v2
 ...
 um vm
 s1 t1 s2 t2

outputFormat

Output a single integer representing the maximum number of roads that can be removed while still satisfying the conditions. If it is impossible to satisfy the conditions, output \(-1\).

sample

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

2