#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000 + 7;
const double esp = 1e-13;
queue<int> Q;
int x, y, u, n, m, ans, f[3000 + 10][3000 + 10], d[3000 + 10], s1, t1, l1, s2,
    t2, l2;
vector<int> a[3000 + 10];
void bfs(int uu) {
  while (!Q.empty()) Q.pop();
  Q.push(uu);
  for (int j = 1; j <= n; j++)
    if (j == uu)
      d[j] = 0;
    else
      d[j] = INF;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (typeof((a[u]).begin()) it = (a[u]).begin(); it != (a[u]).end(); it++) {
      if (d[*it] > d[u] + 1) {
        Q.push(*it);
        d[*it] = d[u] + 1;
      }
    }
  }
  for (int j = 1; j <= n; j++) f[uu][j] = d[j];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) bfs(i);
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  if (f[s1][t1] > l1 || f[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  ans = f[s1][t1] + f[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (f[s1][i] + f[i][j] + f[j][t1] <= l1 &&
          f[s2][i] + f[i][j] + f[j][t2] <= l2)
        ans = min(ans, f[s1][i] + f[s2][i] + f[i][j] + f[j][t1] + f[j][t2]);
      if (f[s1][j] + f[j][i] + f[i][t1] <= l1 &&
          f[s2][i] + f[i][j] + f[j][t2] <= l2)
        ans = min(ans, f[t1][i] + f[i][j] + f[j][s1] + f[s2][i] + f[j][t2]);
    }
  cout << m - ans;
}
