#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return (a ? gcd(b % a, a) : b); }
long long power(long long a, long long n) {
  long long p = 1;
  while (n > 0) {
    if (n % 2) {
      p = p * a;
    }
    n >>= 1;
    a *= a;
  }
  return p;
}
const int maxN = 3000;
int dist[maxN + 10][maxN + 10], n, m, a, b, s[2], t[2], l[2], ans;
vector<int> e[maxN + 10];
void bfs(int u) {
  memset(dist[u], -1, sizeof(dist[u]));
  dist[u][u] = 0;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < e[x].size(); i++) {
      int y = e[x][i];
      if (dist[u][y] == -1) {
        dist[u][y] = dist[u][x] + 1;
        q.push(y);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  for (int i = 0; i < 2; i++) {
    cin >> s[i] >> t[i] >> l[i];
    s[i]--;
    t[i]--;
  }
  for (int i = 0; i < n; i++) {
    bfs(i);
  }
  if (dist[s[0]][t[0]] > l[0] || dist[s[1]][t[1]] > l[1]) return cout << -1, 0;
  ans = dist[s[0]][t[0]] + dist[s[1]][t[1]];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int d1 = dist[s[0]][i] + dist[i][j] + dist[j][t[0]];
      int d2 = dist[s[1]][i] + dist[i][j] + dist[j][t[1]];
      if (d1 <= l[0] && d2 <= l[1]) {
        ans = min(ans, d1 + d2 - dist[i][j]);
      }
      d2 = dist[t[1]][i] + dist[i][j] + dist[j][s[1]];
      if (d1 <= l[0] && d2 <= l[1]) {
        ans = min(ans, d1 + d2 - dist[i][j]);
      }
      d1 = dist[t[0]][i] + dist[i][j] + dist[j][s[0]];
      if (d1 <= l[0] && d2 <= l[1]) {
        ans = min(ans, d1 + d2 - dist[i][j]);
      }
      d2 = dist[s[1]][i] + dist[i][j] + dist[j][t[1]];
      if (d1 <= l[0] && d2 <= l[1]) {
        ans = min(ans, d1 + d2 - dist[i][j]);
      }
    }
  }
  cout << m - ans;
  return 0;
}
