#include <bits/stdc++.h>
using namespace std;
int dist[3005][3005];
vector<int> v[3005];
void BFS(int n) {
  queue<int> q;
  q.push(n);
  bool seen[3005] = {};
  seen[n] = true;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int e : v[x])
      if (!seen[e]) {
        seen[e] = true;
        dist[n][e] = dist[n][x] + 1;
        q.push(e);
      }
  }
}
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for (int i = 1; i <= N; i++) BFS(i);
  int s, f, t, S, F, T;
  cin >> s >> f >> t >> S >> F >> T;
  if (dist[s][f] > t || dist[S][F] > T) {
    cout << -1;
    return 0;
  }
  int ans = dist[s][f] + dist[S][F];
  for (int i = 1; i <= N; i++)
    for (int j = i + 1; j <= N; j++) {
      int d = min(dist[s][i] + dist[i][j] + dist[j][f],
                  dist[s][j] + dist[j][i] + dist[i][f]);
      int D = min(dist[S][i] + dist[i][j] + dist[j][F],
                  dist[S][j] + dist[j][i] + dist[i][F]);
      if (d <= t && D <= T) ans = min(d + D - dist[i][j], ans);
    }
  cout << M - ans;
}
