| Codeforces Round 302 (Div. 1) |
|---|
| Закончено |
В некоторой стране есть ровно n городов и m двусторонних дорог, соединяющих города. Пронумеруем города некоторым образом целыми числами от 1 до n. Если города a и b соединены дорогой, то за один час вы можете по ней проехать как из города a в город b, так и из города b в город a. Кроме того, сеть дорог такова, что из каждого города можно добраться до любого другого города, двигаясь по дорогам.
Вы хотите разрушить наибольшее количество дорог в стране так, чтобы с помощью оставшихся дорог можно было добраться из города s1 в город t1 не более чем за l1 часов и из города s2 в город t2 не более чем за l2 часов.
Определите, какое максимальное количество дорог можно разрушить так, чтобы удовлетворить условию вашего плана. Если добиться желаемого невозможно, выведите -1.
В первой строке задано два целых числа n, m (1 ≤ n ≤ 3000, 
) — количество городов и дорог в стране соответственно.
Далее в m строках задано описание дорог в виде пар чисел ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Гарантируется, что по заданным в описании дорогам из каждого города можно добраться до любого другого города. Гарантируется, что между каждой парой городов существует не более одной дороги.
Последние две строки содержат по три числа s1, t1, l1 и s2, t2, l2, соответственно (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n).
Выведите единственное число — ответ на задачу. Если план выполнить невозможно, выведите -1.
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 2
0
5 4
1 2
2 3
3 4
4 5
1 3 2
2 4 2
1
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 1
-1
