#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> nei[5000];
int ans[5000][5000];
void bfs(int x) {
  queue<int> q;
  q.push(x);
  ans[x][x] = 0;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    for (int i = 0; i < nei[t].size(); i++) {
      if (ans[x][nei[t][i]] > ans[x][t] + 1) {
        ans[x][nei[t][i]] = ans[x][t] + 1;
        q.push(nei[t][i]);
      }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) ans[i][j] = 12345678;
  int i, j, a, b, s1, e1, t1, s2, e2, t2, maxn = 0;
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    nei[a].push_back(b);
    nei[b].push_back(a);
  }
  cin >> s1 >> e1 >> t1;
  cin >> s2 >> e2 >> t2;
  s1--;
  e1--;
  s2--;
  e2--;
  for (i = 0; i < n; i++) {
    bfs(i);
  }
  int res = 123456789;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (ans[s1][i] + ans[i][j] + ans[j][e1] <= t1 &&
          ans[s2][i] + ans[i][j] + ans[j][e2] <= t2) {
        res = min(
            res, ans[s1][i] + ans[i][j] + ans[j][e1] + ans[s2][i] + ans[j][e2]);
      }
      swap(s2, e2);
      if (ans[s1][i] + ans[i][j] + ans[j][e1] <= t1 &&
          ans[s2][i] + ans[i][j] + ans[j][e2] <= t2) {
        res = min(
            res, ans[s1][i] + ans[i][j] + ans[j][e1] + ans[s2][i] + ans[j][e2]);
      }
      swap(s2, e2);
    }
  }
  if (ans[s1][e1] <= t1 && ans[s2][e2] <= t2) {
    res = min(res, ans[s1][e1] + ans[s2][e2]);
  }
  if (res <= m) {
    cout << m - res;
  } else {
    cout << -1;
  }
  return 0;
}
