#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cout.precision(10);
  cout << fixed;
  int n, m;
  cin >> n >> m;
  vector<vector<int> > adj(n, vector<int>());
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  --s1;
  --t1;
  --s2;
  --t2;
  vector<vector<int> > dist(n, vector<int>(n, -1));
  for (int i = 0; i < n; ++i) {
    vector<int> v(n, 0);
    vector<int> d(n, -1);
    queue<int> q;
    q.push(i);
    q.push(0);
    v[i] = 1;
    d[i] = 0;
    while (!q.empty()) {
      int ii = q.front();
      q.pop();
      int dd = q.front();
      q.pop();
      for (int j : adj[ii])
        if (!v[j]) {
          q.push(j);
          q.push(dd + 1);
          d[j] = dd + 1;
          v[j] = 1;
        }
    }
    for (int j = 0; j < n; ++j) {
      dist[i][j] = d[j];
    }
  }
  int res = -1;
  if (dist[s1][t1] > l1 || dist[s2][t2] > l2) {
    cout << res << endl;
    return 0;
  }
  res = m - dist[s1][t1] - dist[s2][t2];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int dij = dist[i][j];
      int p1 = dist[s1][i] + dij + dist[j][t1];
      int p2 = dist[s2][i] + dij + dist[j][t2];
      if (p1 <= l1 && p2 <= l2) {
        res = max(res, m - (p1 + p2 - dij));
      }
      p2 = dist[s2][j] + dij + dist[i][t2];
      if (p1 <= l1 && p2 <= l2) {
        res = max(res, m - (p1 + p2 - dij));
      }
    }
  }
  cout << res << endl;
  return 0;
}
