#include <bits/stdc++.h>
using namespace std;
long long d[3005][3005];
long long n, m, s1, s2, len1, len2, t1, t2;
vector<long long> g[3005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  long long x, y;
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  cin >> s1 >> t1 >> len1 >> s2 >> t2 >> len2;
  s1--;
  s2--;
  t1--;
  t2--;
  memset(d, -1, sizeof d);
  for (long long i = 0; i < n; i++) {
    queue<long long> q;
    q.push(i);
    d[i][i] = 0;
    while (!q.empty()) {
      long long s = q.front();
      q.pop();
      for (long long j = 0; j < g[s].size(); j++) {
        long long to = g[s][j];
        if (d[i][to] == -1) {
          d[i][to] = d[i][s] + 1;
          q.push(to);
        }
      }
    }
  }
  long long res = 3005;
  for (long long k = 0; k < 2; k++) {
    swap(s1, t1);
    for (long long i = 0; i < n; i++) {
      for (long long j = 0; j < n; j++) {
        pair<long long, long long> p;
        p = {d[s1][i] + d[i][j] + d[j][t1], d[s2][i] + d[i][j] + d[j][t2]};
        if (p.first <= len1 && p.second <= len2) {
          res = min(res, p.first + p.second - d[i][j]);
        }
      }
    }
  }
  if (d[s1][t1] <= len1 && d[s2][t2] <= len2) {
    res = min(res, d[s1][t1] + d[s2][t2]);
  }
  if (res > m) {
    res = -1;
  } else {
    res = m - res;
  }
  cout << res;
}
