#include <bits/stdc++.h>
using namespace std;
vector<int> adj[3001];
int n, m, s1, s2, t1, t2, l1, l2, a, b, ans, di[3001][3001], s, d, v;
void bfs(int u) {
  queue<pair<int, int> > q;
  q.push(make_pair(u, 0));
  while (!q.empty()) {
    s = q.front().first, d = q.front().second;
    q.pop();
    if (di[u][s] != -1) continue;
    di[u][s] = d;
    for (int i = 0; i < adj[s].size(); i++) {
      v = adj[s][i];
      if (di[u][v] == -1) q.push(make_pair(v, d + 1));
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) di[i][j] = -1;
  for (int i = 1; i <= n; i++) bfs(i);
  if (di[s1][t1] > l1 or di[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  ans = di[s1][t1] + di[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        if (di[s1][i] + di[i][j] + di[j][t1] <= l1 and
            di[s2][i] + di[i][j] + di[j][t2] <= l2)
          ans = min(ans,
                    di[s1][i] + di[s2][i] + di[i][j] + di[j][t1] + di[j][t2]);
        if (di[t1][i] + di[i][j] + di[j][s1] <= l1 and
            di[s2][i] + di[i][j] + di[j][t2] <= l2)
          ans = min(ans,
                    di[t1][i] + di[s2][i] + di[i][j] + di[j][s1] + di[j][t2]);
      }
    }
  printf("%d\n", m - ans);
  return 0;
}
