#include <bits/stdc++.h>
using namespace std;
vector<int> V[3002];
int dist[3002][3002];
int n, m;
int minimum(int a, int b) {
  if (a <= b) return a;
  return b;
}
void bfs() {
  for (int i = 0; i <= 3001; i++)
    for (int j = 0; j <= 3001; j++) dist[i][j] = -1;
  queue<pair<int, int> > q;
  for (int i = 1; i <= n; i++) {
    q.push(make_pair(i, 0));
    dist[i][i] = 0;
    while (!q.empty()) {
      pair<int, int> cur = q.front();
      q.pop();
      int curNode = cur.first;
      int curDist = cur.second;
      for (int j = 0; j < V[curNode].size(); j++) {
        if (dist[i][V[curNode][j]] == -1) {
          dist[i][V[curNode][j]] = curDist + 1;
          q.push(make_pair(V[curNode][j], dist[i][V[curNode][j]]));
        }
      }
    }
  }
}
int main(void) {
  scanf("%d%d", &n, &m);
  int ans = m + 1;
  int tempm = m;
  while (tempm--) {
    int a, b;
    scanf("%d%d", &a, &b);
    V[a].push_back(b);
    V[b].push_back(a);
  }
  int s[2], t[2], l[2];
  scanf("%d%d%d", s, t, l);
  scanf("%d%d%d", s + 1, t + 1, l + 1);
  bfs();
  for (int k = 1; k <= 2; k++) {
    swap(s[0], t[0]);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int v[] = {dist[s[0]][i] + dist[i][j] + dist[j][t[0]],
                   dist[s[1]][i] + dist[i][j] + dist[j][t[1]]};
        if (v[0] <= l[0] && v[1] <= l[1]) {
          ans = minimum(ans, v[0] + v[1] - dist[i][j]);
        }
      }
    }
  }
  if (dist[s[0]][t[0]] <= l[0] && dist[s[1]][t[1]] <= l[1])
    ans = minimum(ans, dist[s[0]][t[0]] + dist[s[1]][t[1]]);
  if (ans > m)
    printf("-1\n");
  else
    printf("%d\n", m - ans);
  return 0;
}
