В некоторой стране есть ровно n городов и m двусторонних дорог, соединяющих города. Пронумеруем города некоторым образом целыми числами от 1 до n. Если города a и b соединены дорогой, то за один час вы можете по ней проехать как из города a в город b, так и из города b в город a. Кроме того, сеть дорог такова, что из каждого города можно добраться до любого другого города, двигаясь по дорогам.
Вы хотите разрушить наибольшее количество дорог в стране так, чтобы с помощью оставшихся дорог можно было добраться из города s1 в город t1 не более чем за l1 часов и из города s2 в город t2 не более чем за l2 часов.
Определите, какое максимальное количество дорог можно разрушить так, чтобы удовлетворить условию вашего плана. Если добиться желаемого невозможно, выведите -1.
Выходные данные
Выведите единственное число — ответ на задачу. Если план выполнить невозможно, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 2
|
0
|
|
2
|
5 4
1 2
2 3
3 4
4 5
1 3 2
2 4 2
|
1
|
|
3
|
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 1
|
-1
|