#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, cnt;
int last[3005], q[3005], dis[3005][3005];
int s1, t1, l1, s2, t2, l2;
bool vis[3005];
struct edge {
  int to, next;
} e[6005];
void insert(int u, int v) {
  e[++cnt] = (edge){v, last[u]};
  last[u] = cnt;
  e[++cnt] = (edge){u, last[v]};
  last[v] = cnt;
}
void bfs(int x) {
  memset(vis, 0, sizeof(vis));
  int head = 0, tail = 1;
  q[0] = x;
  vis[x] = 1;
  while (head != tail) {
    int now = q[head];
    head++;
    for (int i = last[now]; i; i = e[i].next)
      if (!vis[e[i].to]) {
        vis[e[i].to] = 1;
        dis[x][e[i].to] = dis[x][now] + 1;
        q[tail++] = e[i].to;
      }
  }
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    int u = read(), v = read();
    insert(u, v);
  }
  for (int i = 1; i <= n; i++) bfs(i);
  s1 = read();
  t1 = read();
  l1 = read();
  s2 = read();
  t2 = read();
  l2 = read();
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  int ans = dis[s1][t1] + dis[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
        ans = min(
            ans, dis[s1][i] + dis[s2][i] + dis[i][j] + dis[j][t1] + dis[j][t2]);
      if (dis[s1][j] + dis[i][j] + dis[i][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
        ans = min(
            ans, dis[s1][j] + dis[s2][i] + dis[i][j] + dis[i][t1] + dis[j][t2]);
    }
  printf("%d\n", m - ans);
  return 0;
}
