题目描述

在这个国家有 $n$ 个城市，城市间由 $m$ 条双向公路连接。城市被编号为 $1$ 到 $n$。如果城市 $a$ 和 $b$ 被公路连接，那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时 $1$ 小时。

你想要破坏最多的公路，但是破坏后必须满足从指定城市 $s_1$ 到 $t_1$ 最短不超过 $l_1$ 小时，且从指定城市 $s_2$ 到 $t_2$ 最短不超过 $l_2$ 小时。

计算在符合条件的情况下能破坏的最多公路数量。如果无论如何都无法满足条件，输出 $-1$。

输入格式

第一行包含两个整数 $n, m\ (1 \leq n \leq 3000,\ n - 1 \leq m \leq \min\{3000, \frac{n(n-1)}{2}\})$，分别代表城市的数量和公路的数量。

下面的 $m$ 行包含描述公路的整数对 $a_i, b_i\ (1 \leq a_i, b_i \leq n, a_i \neq b_i)$。数据保证没有重边。

最后的 $2$ 行每行包含三个整数 $s_1, t_1, l_1$ 和 $s_2, t_2, l_2\ (1 \leq s_i, t_i \leq n,\ 0 \leq l_i \leq 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