#include <bits/stdc++.h>
using namespace std;
int n, m;
int s1, t1, l1, s2, t2, l2;
vector<int> adj[3005];
vector<int> d[3005];
vector<int> dis;
vector<int> getDis(int node) {
  dis = vector<int>(3005);
  for (int i = (0); i < int(n); ++i) dis[i] = 1000000;
  dis[node] = 0;
  queue<int> q;
  q.push(node);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = (0); i < int(adj[cur].size()); ++i) {
      int to = adj[cur][i];
      if (dis[to] != 1000000) continue;
      dis[to] = dis[cur] + 1;
      q.push(to);
    }
  }
  return dis;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (0); i < int(m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  --s1;
  --t1;
  --s2;
  --t2;
  for (int i = (0); i < int(n); ++i) d[i] = getDis(i);
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  int need = d[s1][t1] + d[s2][t2];
  for (int i = (0); i < int(n); ++i)
    for (int j = (0); j < int(n); ++j) {
      int d1 = min(d[s1][i] + d[t1][j], d[s1][j] + d[t1][i]);
      int d2 = min(d[s2][i] + d[t2][j], d[s2][j] + d[t2][i]);
      if (d1 + d[i][j] > l1 || d2 + d[i][j] > l2) continue;
      int tmp = d1 + d2 + d[i][j];
      need = min(need, tmp);
    }
  printf("%d\n", m - need);
}
