#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
void tracer(istream_iterator<string> it) {}
template <typename T, typename... Args>
void tracer(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << " | ";
  tracer(++it, args...);
}
const int INF = 2e9;
const long long LINF = 2e18;
const long long MOD = 1e9 + 7;
const double err = 1e-10;
const int N = 3e3 + 5;
int n, m;
vector<vector<int>> adj(N);
int dis[N][N];
vector<bool> vis(N);
void calcdis() {
  for (int i = 1; i <= n; i++) {
    vis.assign(n + 1, 0);
    vis[i] = 1;
    queue<pair<int, int>> Q;
    for (auto v : adj[i]) {
      Q.push(make_pair(v, 1));
    }
    dis[i][i] = 0;
    while (!Q.empty()) {
      auto pr = Q.front();
      Q.pop();
      int u = pr.first, d = pr.second;
      if (vis[u]) continue;
      dis[i][u] = d;
      vis[u] = 1;
      for (auto v : adj[u]) {
        if (vis[v]) continue;
        Q.push(make_pair(v, d + 1));
      }
    }
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int s1, t1, l1;
  cin >> s1 >> t1 >> l1;
  int s2, t2, l2;
  cin >> s2 >> t2 >> l2;
  int ans = INF;
  calcdis();
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2) {
    ans = min(ans, dis[s1][t1] + dis[s2][t2]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int d1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      int d2 = dis[s2][i] + dis[i][j] + dis[j][t2];
      if (d1 <= l1 && d2 <= l2) {
        ans = min(ans, d1 + d2 - dis[i][j]);
      }
      d2 = dis[s2][j] + dis[i][j] + dis[i][t2];
      if (d2 <= l2 && d1 <= l1) {
        ans = min(ans, d1 + d2 - dis[i][j]);
      }
    }
  }
  cout << (ans <= m ? m - ans : -1) << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  for (int i = 1; i <= T; i++) {
    solve();
  }
  return 0;
}
