#include <bits/stdc++.h>
using namespace std;
vector<int> g[3005];
queue<int> q;
int d[3005][3005];
int n, m, a, b, s1, t1, l1, s2, t2, l2;
int calc(int st, int m1, int m2, int ed) {
  return min(d[st][m1] + d[m1][m2] + d[m2][ed],
             d[ed][m1] + d[m1][m2] + d[m2][st]);
}
int main() {
  int i, j, id;
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++) g[i].clear();
  for (i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  scanf("%d %d %d %d %d %d", &s1, &t1, &l1, &s2, &t2, &l2);
  s1--;
  t1--;
  s2--;
  t2--;
  for (i = 0; i < n; i++) {
    d[i][i] = 1;
    q.push(i);
    while (!q.empty()) {
      id = q.front();
      q.pop();
      for (j = 0; j < g[id].size(); j++) {
        if (d[i][g[id][j]] == 0) {
          d[i][g[id][j]] = d[i][id] + 1;
          q.push(g[id][j]);
        }
      }
    }
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) d[i][j]--;
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  int ans = d[s1][t1] + d[s2][t2];
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      if (calc(s1, i, j, t1) <= l1 && calc(s2, i, j, t2) <= l2) {
        ans = min(ans, calc(s1, i, j, t1) + calc(s2, i, j, t2) - d[i][j]);
      }
    }
  printf("%d\n", m - ans);
}
