#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30, MOD = 1000000007;
const long double eps = 1e-9;
vector<int> v[5000];
int d[3100][3100];
queue<int> q;
bool was[5000];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int u1, u2, u;
  for (int i = 0; i < (int)m; i++) {
    scanf("%d%d", &u1, &u2);
    v[u1].push_back(u2);
    v[u2].push_back(u1);
  }
  for (int i = 1; i <= (int)n; i++) {
    memset(was, 0, sizeof(was));
    q.push(i);
    was[i] = true;
    while (!q.empty()) {
      u = q.front();
      for (int j = 0; j < (int)v[u].size(); j++)
        if (!was[v[u][j]]) {
          d[i][v[u][j]] = d[i][u] + 1;
          q.push(v[u][j]);
          was[v[u][j]] = true;
        }
      q.pop();
    }
  }
  int s1, t1, l1, s2, t2, l2;
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  int ans = d[s1][t1] + d[s2][t2];
  int z1, z2;
  for (int i = 1; i <= (int)n; i++) {
    for (int j = i + 1; j <= n; j++) {
      z1 = min(d[s1][i] + d[j][t1], d[s1][j] + d[i][t1]);
      z2 = min(d[s2][i] + d[j][t2], d[s2][j] + d[i][t2]);
      if (z1 + d[i][j] > l1 || z2 + d[i][j] > l2) continue;
      ans = min(ans, z1 + z2 + d[i][j]);
    }
  }
  cout << m - ans;
  return 0;
}
