#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
inline int add(int a, int b) {
  if ((a += b) >= P) a -= P;
  return a;
}
inline int sub(int a, int b) {
  if ((a -= b) < 0) a += P;
  return a;
}
inline int mul(int a, int b) { return 1ll * a * b % P; }
inline int kpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) r = mul(r, a);
  }
  return r;
}
const int N = 3030;
int n, m;
vector<int> G[N];
int dis[N][N];
bool vis[N];
int s[2], t[2], l[2];
void bfs(int st, int dis[N]) {
  memset(vis, 0, sizeof(vis));
  vector<int> q;
  q.push_back(st);
  vis[st] = 1;
  for (int h = (0); h < ((int)q.size()); h++) {
    int u = q[h];
    for (auto v : G[u])
      if (!vis[v]) {
        q.push_back(v);
        dis[v] = dis[u] + 1;
        vis[v] = 1;
      }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (0); i < (m); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    G[u].push_back(v), G[v].push_back(u);
  }
  for (int i = (0); i < (2); i++) scanf("%d%d%d", s + i, t + i, l + i);
  for (int i = (0); i < (2); i++) s[i]--, t[i]--;
  for (int i = (0); i < (n); i++) bfs(i, dis[i]);
  if (dis[s[0]][t[0]] > l[0] || dis[s[1]][t[1]] > l[1]) {
    puts("-1");
    return 0;
  }
  int ans = m - dis[s[0]][t[0]] - dis[s[1]][t[1]];
  for (int u = (0); u < (n); u++)
    for (int v = (0); v < (n); v++) {
      int d = 0;
      if (dis[s[0]][u] + dis[u][v] + dis[v][t[0]] <= l[0] &&
          dis[s[1]][u] + dis[t[1]][v] + dis[u][v] <= l[1]) {
        for (int i = (0); i < (2); i++) d += dis[s[i]][u];
        for (int i = (0); i < (2); i++) d += dis[v][t[i]];
        ans = max(ans, m - d - dis[u][v]);
      }
      swap(s[0], t[0]);
      d = 0;
      if (dis[s[0]][u] + dis[u][v] + dis[v][t[0]] <= l[0] &&
          dis[s[1]][u] + dis[t[1]][v] + dis[u][v] <= l[1]) {
        for (int i = (0); i < (2); i++) d += dis[s[i]][u];
        for (int i = (0); i < (2); i++) d += dis[v][t[i]];
        ans = max(ans, m - d - dis[u][v]);
      }
      swap(s[0], t[0]);
    }
  printf("%d\n", ans);
  return 0;
}
