#include <bits/stdc++.h>
using namespace std;
int n, m, d[3003][3003], s[2], t[2], l[2], start[4], re;
vector<int> v[3003];
void input() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for (int i = 0; i < 2; i++) scanf("%d %d %d", &s[i], &t[i], &l[i]);
  start[0] = s[0];
  start[1] = t[0];
  start[2] = s[1];
  start[3] = t[1];
}
void dijkstra(int st) {
  priority_queue<pair<int, int> > pq;
  int p = st;
  pq.push(pair<int, int>(0, p));
  d[p][p] = 0;
  while (!pq.empty()) {
    pair<int, int> cur = pq.top();
    pq.pop();
    int curd = -cur.first;
    int p = cur.second;
    if (curd > d[st][p]) continue;
    for (int i = 0; i < v[p].size(); i++) {
      int nxt = v[p][i];
      if (d[st][nxt] > curd + 1) {
        d[st][nxt] = curd + 1;
        pq.push(pair<int, int>(-d[st][nxt], nxt));
      }
    }
  }
}
void solve() {
  input();
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) d[i][j] = 1e6;
    dijkstra(i);
  }
  re = 1e6;
  if (d[s[0]][t[0]] <= l[0] && d[s[1]][t[1]] <= l[1])
    re = d[s[0]][t[0]] + d[s[1]][t[1]];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[s[0]][i] + d[i][j] + d[j][t[0]] <= l[0] &&
          d[s[1]][i] + d[i][j] + d[j][t[1]] <= l[1] &&
          re > d[s[0]][i] + d[i][j] + d[j][t[0]] + d[s[1]][i] + d[j][t[1]])
        re = d[s[0]][i] + d[i][j] + d[j][t[0]] + d[s[1]][i] + d[j][t[1]];
      if (d[s[0]][i] + d[i][j] + d[j][t[0]] <= l[0] &&
          d[s[1]][j] + d[i][j] + d[i][t[1]] <= l[1] &&
          re > d[s[0]][i] + d[i][j] + d[j][t[0]] + d[s[1]][j] + d[i][t[1]])
        re = d[s[0]][i] + d[i][j] + d[j][t[0]] + d[s[1]][j] + d[i][t[1]];
    }
  }
  if (re >= 1e6 || m - re < 0)
    re = -1;
  else
    re = m - re;
  printf("%d\n", re);
}
int main(void) {
  solve();
  return 0;
}
