B. Разрушение дорог
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В некоторой стране есть ровно 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