#include <bits/stdc++.h>
using namespace std;
const int N = 3005, M = 6005;
int n, m, tot, cnt, s1, s2, t1, t2, l1, l2, lnk[N], nxt[M], son[M], dis[N][N];
bool vis[N];
queue<int> q;
void add(int x, int y) { nxt[++tot] = lnk[x], lnk[x] = tot, son[tot] = y; }
void bfs(int id) {
  memset(vis, 0, sizeof vis), vis[id] = 1;
  memset(dis[id], 63, sizeof dis[id]), dis[id][id] = 0;
  while (!q.empty()) q.pop();
  q.push(id);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    vis[x] = 1;
    for (int j = lnk[x]; j; j = nxt[j]) {
      if (!vis[son[j]]) {
        vis[son[j]] = 1;
        dis[id][son[j]] = dis[id][x] + 1;
        q.push(son[j]);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, x, y; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  for (int i = 1; i <= n; ++i) bfs(i);
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) return printf("-1"), 0;
  cnt = dis[s1][t1] + dis[s2][t2];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (l1 >= dis[s1][i] + dis[i][j] + dis[j][t1] &&
          l2 >= dis[s2][i] + dis[i][j] + dis[j][t2])
        cnt = min(
            cnt, dis[s1][i] + dis[j][t1] + dis[i][j] + dis[s2][i] + dis[j][t2]);
      if (l1 >= dis[s1][j] + dis[i][j] + dis[i][t1] &&
          l2 >= dis[s2][i] + dis[i][j] + dis[j][t2])
        cnt = min(
            cnt, dis[s1][j] + dis[i][t1] + dis[i][j] + dis[s2][i] + dis[j][t2]);
    }
  }
  printf("%d\n", m - cnt);
  return 0;
}
