#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
int main() {
  int n, m;
  cin >> n >> m;
  std::vector<std::vector<int> > nb(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    nb[a].push_back(b);
    nb[b].push_back(a);
  }
  int s1, l1, t1, s2, l2, t2;
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  s1--;
  s2--;
  t1--;
  t2--;
  int ans = 0;
  std::vector<std::vector<int> > dist(n, std::vector<int>(n));
  for (int f = 0; f < n; f++) {
    std::vector<int> u(n, -1);
    deque<int> q;
    q.push_back(f);
    u[f] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop_front();
      for (int i = 0; i < nb[v].size(); i++) {
        if (-1 == u[nb[v][i]]) {
          q.push_back(nb[v][i]);
          u[nb[v][i]] = u[v] + 1;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      dist[f][i] = u[i];
    }
  }
  if ((dist[s1][t1] > l1) || (dist[s2][t2] > l2)) {
    cout << -1;
    return 0;
  }
  ans = dist[s1][t1] + dist[s2][t2];
  for (int f = 0; f < n; f++) {
    for (int l = 0; l < n; l++) {
      int b = dist[f][l];
      if ((dist[s1][f] + b + dist[l][t1]) > l1) continue;
      if ((dist[s2][f] + b + dist[l][t2]) > l2) continue;
      ans = min(ans, dist[s1][f] + b + dist[l][t1] + dist[s2][f] + dist[l][t2]);
    }
  }
  swap(s2, t2);
  for (int f = 0; f < n; f++) {
    for (int l = 0; l < n; l++) {
      int b = dist[f][l];
      if ((dist[s1][f] + b + dist[l][t1]) > l1) continue;
      if ((dist[s2][f] + b + dist[l][t2]) > l2) continue;
      ans = min(ans, dist[s1][f] + b + dist[l][t1] + dist[s2][f] + dist[l][t2]);
    }
  }
  cout << m - ans;
}
