#include <bits/stdc++.h>
using namespace std;
const double eps = 1.0e-11;
const double pi = acos(-1.0);
int n, m;
vector<vector<int> > g;
void bfs(int start, vector<int>& v) {
  queue<int> q;
  q.push(start);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    for (int i = 0; i < g[cur].size(); i++) {
      int to = g[cur][i];
      if (v[to] == 0 && to != start) {
        q.push(to);
        v[to] = v[cur] + 1;
      }
    }
  }
}
int main() {
  cin >> n >> m;
  g.resize(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int s1, s2, t1, t2, l1, l2;
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  s1--;
  s2--;
  t1--;
  t2--;
  vector<vector<int> > d;
  for (int i = 0; i < n; i++) {
    d.push_back(vector<int>(n));
    bfs(i, d.back());
  }
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  if (s1 == t1 && s2 == t2) {
    cout << m;
    return 0;
  }
  if (s1 == t1) {
    cout << m - d[s2][t2];
    return 0;
  }
  if (s2 == t2) {
    cout << m - d[s1][t1];
    return 0;
  }
  int res = max(0, m - d[s1][t1] - d[s2][t2]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int cur1 = d[s1][i] + d[i][j] + d[j][t1];
      int cur2 = d[s2][i] + d[i][j] + d[j][t2];
      int cur3 = d[s2][j] + d[j][i] + d[i][t2];
      if (cur1 <= l1 && cur2 <= l2) {
        int q = d[s1][i] + d[s2][i] + d[j][t1] + d[j][t2] + d[i][j];
        if (s1 == s2) q -= d[s1][i];
        if (t1 == t2) q -= d[j][t1];
        res = max(res, m - q);
      }
      if (cur1 <= l1 && cur3 <= l2) {
        int q = d[s1][i] + d[s2][j] + d[j][t1] + d[i][t2] + d[i][j];
        if (s1 == t2) q -= d[s1][i];
        if (t1 == s2) q -= d[j][t1];
        res = max(res, m - q);
      }
    }
  }
  cout << res;
  return 0;
}
