#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 10;
int n, m, s1, s2, f1, f2, l1, l2, ans = 2000000007;
vector<int> d[MAXN];
int dist[MAXN][MAXN];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    d[x].push_back(y);
    d[y].push_back(x);
  }
  cin >> s1 >> f1 >> l1;
  cin >> s2 >> f2 >> l2;
  memset(dist, 31, sizeof(dist));
  for (int i = 1; i <= n; i++) {
    queue<int> o;
    o.push(i);
    dist[i][i] = 0;
    while (!o.empty()) {
      int x = o.front();
      o.pop();
      for (int j = 0; j < d[x].size(); j++)
        if (dist[i][d[x][j]] > dist[i][x] + 1) {
          dist[i][d[x][j]] = dist[i][x] + 1;
          o.push(d[x][j]);
        }
    }
  }
  if (dist[s1][f1] > l1 || dist[s2][f2] > l2) {
    cout << -1;
    return 0;
  }
  ans = dist[s1][f1] + dist[s2][f2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int x = min(dist[s1][i] + dist[f1][j], dist[f1][i] + dist[s1][j]),
          y = min(dist[s2][i] + dist[f2][j], dist[f2][i] + dist[s2][j]);
      if (x + dist[i][j] <= l1 && y + dist[i][j] <= l2)
        ans = min(ans, x + y + dist[i][j]);
    }
  cout << m - ans;
}
