#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m, a, b, res, s1, t1, l1, s2, t2, l2;
int Dis[4000][4000];
vector<int> Graph[5000];
queue<int> Q;
void CalcDistances();
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &a, &b);
    Graph[a].push_back(b);
    Graph[b].push_back(a);
  }
  CalcDistances();
  scanf("%d %d %d", &s1, &t1, &l1);
  scanf("%d %d %d", &s2, &t2, &l2);
  if (Dis[s1][t1] > l1 || Dis[s2][t2] > l2)
    printf("-1\n");
  else {
    res = Dis[s1][t1] + Dis[s2][t2];
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        int dis = min(Dis[s1][i] + Dis[s2][i],
                      min(Dis[s1][i] + Dis[s2][j], Dis[s1][j] + Dis[s2][i])) +
                  Dis[i][j] +
                  min(Dis[j][t1] + Dis[i][t2],
                      min(Dis[j][t1] + Dis[j][t2], Dis[i][t1] + Dis[j][t2]));
        int dis1 =
            min(Dis[s1][i] + Dis[j][t1], Dis[s1][j] + Dis[i][t1]) + Dis[i][j];
        int dis2 =
            min(Dis[s2][i] + Dis[j][t2], Dis[s2][j] + Dis[i][t2]) + Dis[i][j];
        if (dis1 <= l1 && dis2 <= l2) res = min(res, dis);
      }
    printf("%d\n", m - res);
  }
}
void CalcDistances() {
  for (int i = 1; i <= n; i++) {
    Q.push(i);
    while (!Q.empty()) {
      int v = Q.front();
      Q.pop();
      for (int j = 0; j < (int)(Graph[v]).size(); j++) {
        int u = Graph[v][j];
        if (Dis[i][u] == 0 && u != i) {
          Dis[i][u] = Dis[i][v] + 1;
          Q.push(u);
        }
      }
    }
  }
}
