#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 100;
vector<long long int> v[N];
long long int d[N][N];
int main() {
  long long int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    long long int u1, u2;
    cin >> u1 >> u2;
    u1--;
    u2--;
    v[u1].emplace_back(u2);
    v[u2].emplace_back(u1);
  }
  memset(d, 63, sizeof(d));
  for (int i = 0; i < n; i++) {
    queue<long long int> q;
    while (q.size() > 0) q.pop();
    q.push(i);
    d[i][i] = 0;
    while (q.size() > 0) {
      long long int l = q.front();
      for (int u : v[l])
        if (d[i][u] > d[i][l] + 1) {
          d[i][u] = d[i][l] + 1;
          q.push(u);
        }
      q.pop();
    }
  }
  long long int s1, s2, t1, t2, l1, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  s1--;
  s2--;
  t1--;
  t2--;
  if (d[s1][t1] > l1 || d[s2][t2] > l2) return cout << -1, 0;
  long long int mas = d[s1][t1] + d[s2][t2];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (min(d[s1][i] + d[i][j] + d[j][t1], d[s1][j] + d[i][j] + d[i][t1]) <=
              l1 &&
          min(d[s2][j] + d[i][j] + d[i][t2], d[s2][i] + d[i][j] + d[j][t2]) <=
              l2) {
        mas = min(
            mas,
            d[i][j] + min(d[s1][i] + d[j][t1] + d[s2][i] + d[j][t2],
                          min(d[s1][j] + d[i][t1] + d[s2][i] + d[j][t2],
                              min(d[s1][i] + d[j][t1] + d[s2][j] + d[i][t2],
                                  d[s1][j] + d[i][t1] + d[s2][j] + d[i][t2]))));
      }
    }
  }
  cout << m - mas;
}
