#include <bits/stdc++.h>
using namespace std;
const int NN = 3111;
int o[NN], aa[NN * 2][2], dist[NN][NN];
int n, m, tot, S1, T1, S2, T2, L1, L2;
inline void addedge(int p, int q) {
  tot++;
  aa[tot][1] = q;
  aa[tot][0] = o[p];
  o[p] = tot;
}
void bfs(int S, int *dist) {
  for (int i = 1; i <= n; i++) dist[i] = 999999999;
  static int que[NN];
  int head = 0, tail = 1;
  dist[S] = 0;
  que[1] = S;
  static bool vt[NN];
  memset(vt, 0, sizeof(vt));
  vt[S] = true;
  while (head < tail) {
    int x = que[++head];
    for (int p = o[x]; p; p = aa[p][0]) {
      int y = aa[p][1];
      if (!vt[y]) {
        vt[y] = true;
        dist[y] = dist[x] + 1;
        que[++tail] = y;
      }
    }
  }
}
int work() {
  int ans = m + 1;
  if (dist[S1][T1] <= L1 && dist[S2][T2] <= L2)
    ans = min(dist[S1][T1] + dist[S2][T2], ans);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (dist[S1][i] + dist[i][j] + dist[j][T1] > L1) continue;
      if (dist[S2][i] + dist[i][j] + dist[j][T2] > L2) continue;
      ans = min(ans, dist[S1][i] + dist[S2][i] + dist[i][j] + dist[j][T1] +
                         dist[j][T2]);
    }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  int i, x, y;
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    addedge(x, y), addedge(y, x);
  }
  scanf("%d%d%d%d%d%d", &S1, &T1, &L1, &S2, &T2, &L2);
  for (i = 1; i <= n; i++) bfs(i, dist[i]);
  int ans = m + 1;
  ans = min(ans, work());
  swap(S1, T1);
  ans = min(ans, work());
  if (ans == m + 1)
    printf("-1\n");
  else
    printf("%d\n", m - ans);
  return 0;
}
