#include <bits/stdc++.h>
using namespace std;
int n, m, s1, s2, t1, t2, l1, l2, res;
vector<int> a[3005];
int que[3005], d[3005][3005];
bool dau[3005];
void bfs(int s) {
  int las = 1, fir = 1;
  que[1] = s;
  d[s][s] = 0;
  while (las >= fir) {
    int u = que[fir++];
    for (int i = 0; i < a[u].size(); i++) {
      int v = a[u][i];
      if (d[s][v] == -1) {
        d[s][v] = d[s][u] + 1;
        que[++las] = v;
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[x].push_back(y);
    a[y].push_back(x);
  }
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  memset(d, 255, sizeof(d));
  for (int i = 1; i <= n; i++) bfs(i);
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  res = m - (d[s1][t1] + d[s2][t2]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int kc1 = min(d[i][s1] + d[j][t1], d[i][t1] + d[j][s1]) + d[i][j];
      int kc2 = min(d[i][s2] + d[j][t2], d[i][t2] + d[j][s2]) + d[i][j];
      if (kc1 <= l1 && kc2 <= l2) res = max(res, m - (kc1 + kc2 - d[i][j]));
    }
  printf("%d", res);
  return 0;
}
