在魔法王国中，有 n 座魔法城堡，从 1\to n 编号。1 号城堡是王国的魔法中心。

城堡间由 m 条双向魔法通道连通，通过每一条通道都需要消耗 1 单位魔力。

现在魔法王国打算拆除一些低效的魔法通道以节省魔力维持成本，但必须保证主要魔法线路的畅通。

具体来说，拆除通道后，从魔法中心出发，必须能到达s_1号与 s_2 号城堡，且到达这两座城堡所需的最短魔力消耗分别不超过t_1与 t_2（这是两个独立的条件，不需要先到s_1再到 s_2）。

魔法王国的魔法师们想请你计算，在满足上述条件的情况下，最多可以拆除多少条魔法通道。如果无论如何都无法满足条件，则输出 -1。

第一行两个正整数 n, m，表示城堡数量与魔法通道数量。

接下来 m 行，每行两个正整数 x, y，表示连接 x 号城堡与 y 号城堡的一条魔法通道。

最后一行四个整数，分别是s_1,t_1,s_2,t_2。

仅一行一个整数，表示最多可以拆除的魔法通道数量。

对于 30\% 的数据，n,m \le 15；   

另有 20\% 的数据，n \le 100，m = n-1；   

另有 30\% 的数据，s_1 = s_2；  

对于 100\% 的数据，2 \le n,m \le 3000，1\le x,y \le n，2 \le s_1,s_2 \le n，0 \le t_1,t_2 \le n。