#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)3e3 + 10;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
const double eps = 1e-9;
int n, m, q[maxn];
long long d[maxn][maxn];
vector<int> g[maxn];
void bfs(int v) {
  int s = v;
  for (int i = 1; i <= n; ++i) d[v][i] = inf;
  d[s][v] = 0;
  int l = 0, r = 0, to;
  q[r++] = v;
  while (l < r) {
    v = q[l++];
    for (int i = 0; i < (int)g[v].size(); ++i) {
      to = g[v][i];
      if (d[s][to] > d[s][v] + 1) {
        d[s][to] = d[s][v] + 1;
        q[r++] = to;
      }
    }
  }
  return;
}
int u, v, s1, t1, l1, s2, t2, l2;
long long ans;
void solve() {
  int d1, d2;
  for (int l = 1; l <= n; ++l)
    for (int r = 1; r <= n; ++r) {
      d1 = d[s1][l] + d[l][r] + d[r][t1];
      d2 = d[s2][l] + d[l][r] + d[r][t2];
      if (d1 > l1) continue;
      if (d2 > l2) continue;
      ans = max(ans, m - d1 - d2 + d[l][r]);
    }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) bfs(i);
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  ans = m - d[s1][t1] - d[s2][t2];
  solve();
  swap(s1, t1);
  solve();
  swap(s2, t2);
  solve();
  swap(s1, t1);
  solve();
  cout << ans;
  return 0;
}
