CF543B Destroying Roads

在这个国家有$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$ 。 感谢@KSkun 提供的翻译