#include <bits/stdc++.h>
using namespace std;
inline int ABS(int a) {
  if (a < 0) return (-a);
  return a;
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline int powmod(int x, int n, int _mod) {
  int res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int lcm(int a, int b) { return a / (gcd(a, b) * b); }
inline int bitCount(unsigned int i) { return __builtin_popcount(i); }
inline void cinarr(int x[], int n) {
  for (int i = 0; i < (n); ++i) cin >> (x[i]);
}
inline void cinvec(vector<int> &arr, int n) {
  for (int i = 0; i < (n); ++i) {
    int x;
    cin >> (x);
    arr.push_back(x);
  };
}
const int v5 = 100000;
const int v9 = 1000000000;
const int v6 = 1000000;
int n, m, k, c = 0, s1, t1, l1, s2, t2, l2;
int a[30001];
vector<int> v;
vector<int> g[3001];
int sp[3001][3001];
void bfs(int st) {
  queue<int> q;
  q.push(st);
  while (!q.empty()) {
    int s = q.front();
    q.pop();
    for (int i = (0); i < (int(g[s].size())); ++i) {
      if (sp[st][g[s][i]] == -1 || sp[st][g[s][i]] > sp[st][s] + 1) {
        sp[st][g[s][i]] = sp[st][s] + 1;
        sp[g[s][i]][st] = sp[st][g[s][i]];
      }
      if (a[g[s][i]] != st) {
        a[g[s][i]] = st;
        q.push(g[s][i]);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for (int i = (0); i < (1 + n); ++i)
    for (int j = (0); j < (1 + n); ++j) sp[i][j] = -1;
  for (int i = (0); i < (m); ++i) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = (1); i < (1 + n); ++i) {
    sp[i][i] = 0;
    bfs(i);
  }
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  if (sp[s1][t1] == -1 || sp[s1][t1] > l1 || sp[s2][t2] == -1 ||
      sp[s2][t2] > l2) {
    cout << -1 << "\n";
    return 0;
  }
  c = sp[s1][t1] + sp[s2][t2];
  for (int i = (1); i < (1 + n); ++i)
    for (int b = (1); b < (1 + n); ++b)
      if (sp[i][b] + min(sp[s1][i] + sp[t1][b], sp[s1][b] + sp[t1][i]) <= l1 &&
          sp[i][b] + min(sp[s2][b] + sp[t2][i], sp[s2][i] + sp[t2][b]) <= l2)
        c = min(c, sp[i][b] +
                       min(sp[s1][i] + sp[t1][b], sp[s1][b] + sp[t1][i]) +
                       min(sp[s2][b] + sp[t2][i], sp[s2][i] + sp[t2][b]));
  cout << m - c << "\n";
  return 0;
}
