#include <bits/stdc++.h>
using namespace std;
int res, n, m;
vector<int> g[3333];
int s1, t1, l1, s2, t2, l2;
int d[3333][3333];
int q[3333], qn;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    qn = 0;
    d[i][i] = 1;
    q[qn++] = i;
    for (int j = 0; j < qn; j++) {
      for (int k = 0; k < g[q[j]].size(); k++) {
        int num = g[q[j]][k];
        if (!d[i][num]) {
          d[i][num] = d[i][q[j]] + 1;
          q[qn++] = num;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      d[i][j]--;
    }
  }
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1 << endl;
    return 0;
  }
  res = d[s1][t1] + d[s2][t2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2) {
        res = min(res, d[s1][i] + d[j][t1] + d[s2][i] + d[i][j] + d[j][t2]);
      }
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[t2][i] + d[i][j] + d[j][s2] <= l2) {
        res = min(res, d[s1][i] + d[j][t1] + d[t2][i] + d[i][j] + d[j][s2]);
      }
    }
  }
  cout << m - res << endl;
  return 0;
}
