#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
struct node {
  int nxt, to;
} edge[N * 2];
int head[N], cnt = 1, G[N][N];
int s1, t1, l1, s2, t2, l2;
bool vis[N], inq[N];
queue<int> Q;
inline void add(int x, int y) {
  edge[++cnt].to = y;
  edge[cnt].nxt = head[x];
  head[x] = cnt;
}
inline void link(int x, int y) {
  add(x, y);
  add(y, x);
}
inline void bfs(int x) {
  Q.push(x);
  G[x][x] = 0;
  int n, t;
  while (!Q.empty()) {
    n = Q.front();
    Q.pop();
    for (int i = head[n]; i; i = edge[i].nxt) {
      t = edge[i].to;
      if (!G[x][t] && t != x) {
        G[x][t] = G[x][n] + 1;
        Q.push(t);
      }
    }
  }
}
int main() {
  int n, m, x, y;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    link(x, y);
  }
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  for (int i = 1; i <= n; i++) bfs(i);
  if (G[s1][t1] > l1 || G[s2][t2] > l2) {
    printf("-1");
    return 0;
  }
  int ans = G[s1][t1] + G[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int a = min(G[s1][i], G[s1][j]);
      int b = min(G[i][t1], G[j][t1]);
      int c = min(G[s2][i], G[s2][i]);
      int d = min(G[i][t2], G[j][t2]);
      if (a + G[i][j] + b > l1) continue;
      if (c + G[i][j] + d > l2) continue;
      ans = min(ans, a + b + c + d + G[i][j]);
    }
  printf("%d\n", m - ans);
  return 0;
}
