#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int kMaxN = 3000 + 2;
vector<int> edges[kMaxN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    edges[a].emplace_back(b);
    edges[b].emplace_back(a);
  }
  array<int, 3> q[2];
  for (int i : {0, 1}) {
    for (int j : {0, 1, 2}) {
      cin >> q[i][j];
    }
  }
  vector<vector<int>> d(n + 1, vector<int>(n + 1, -1));
  for (int i = 1; i <= n; ++i) {
    queue<int> q;
    q.emplace(i);
    d[i][i] = 0;
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      for (int v : edges[u]) {
        if (d[i][v] == -1) {
          d[i][v] = d[i][u] + 1;
          q.emplace(v);
        }
      }
    }
  }
  if (d[q[0][0]][q[0][1]] > q[0][2] || d[q[1][0]][q[1][1]] > q[1][2]) {
    cout << "-1\n";
    return 0;
  }
  int best = d[q[0][0]][q[0][1]] + d[q[1][0]][q[1][1]];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      int common = d[i][j];
      for (int k1 : {0, 1}) {
        for (int k2 : {0, 1}) {
          int dist1 = d[i][q[0][k1]] + d[j][q[0][k1 ^ 1]] + common;
          int dist2 = d[i][q[1][k2]] + d[j][q[1][k2 ^ 1]] + common;
          if (dist1 > q[0][2] || dist2 > q[1][2]) {
            continue;
          }
          best = min(best, dist1 + dist2 - common);
        }
      }
    }
  }
  cout << m - best << '\n';
  return 0;
}
