#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 3e3 + 5;
const int mod = 1e9 + 7;
struct Edge {
  int to, next;
} E[maxm << 1];
int head[maxm], cnt;
inline void init() {
  memset(head, -1, sizeof head);
  cnt = 0;
}
inline void addedge(int u, int v) {
  E[cnt].to = v;
  E[cnt].next = head[u];
  head[u] = cnt++;
}
int g[maxm][maxm];
inline void bfs(int s) {
  queue<int> q;
  q.push(s);
  g[s][s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = E[i].next) {
      int v = E[i].to;
      if (g[s][v] == -1) {
        g[s][v] = g[s][u] + 1;
        q.push(v);
      }
    }
  }
}
inline void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  init();
  for (int i = 1; i < m + 1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addedge(u, v);
    addedge(v, u);
  }
  int s1, t1, l1, s2, t2, l2;
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  memset(g, -1, sizeof g);
  for (int i = 1; i < n + 1; i++) bfs(i);
  int res = m + 1;
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < n + 1; j++) {
      int a = g[s1][i] + g[i][j] + g[j][t1];
      int b = g[s2][i] + g[i][j] + g[j][t2];
      if (a <= l1 && b <= l2) res = min(res, a + b - g[i][j]);
      int c = g[s1][j] + g[j][i] + g[i][t1];
      if (c <= l1 && b <= l2) res = min(res, c + b - g[i][j]);
    }
  }
  if (g[s1][t1] <= l1 && g[s2][t2] <= l2) res = min(res, g[s1][t1] + g[s2][t2]);
  if (res > m)
    puts("-1");
  else
    printf("%d\n", m - res);
}
int main() {
  solve();
  return 0;
}
