#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 100005;
vector<int> g[3001];
int d[3001][3001];
int n, m;
int s[2], t[2], l[2];
int main() {
  cin >> n >> m;
  int u, v;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    memset(d[i], -1, sizeof(d[i]));
    queue<int> q;
    d[i][i] = 0;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int j = 0; j < g[u].size(); j++) {
        int v = g[u][j];
        if (d[i][v] == -1) d[i][v] = d[i][u] + 1, q.push(v);
      }
    }
  }
  for (int i = 0; i < 2; i++) cin >> s[i] >> t[i] >> l[i];
  if (d[s[0]][t[0]] > l[0] || d[s[1]][t[1]] > l[1]) {
    cout << -1 << endl;
    return 0;
  }
  int ans = d[s[0]][t[0]] + d[s[1]][t[1]];
  for (int k = 0; k < 2; k++) {
    swap(s[0], t[0]);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int l0 = d[s[0]][i] + d[i][j] + d[j][t[0]],
            l1 = d[s[1]][i] + d[i][j] + d[j][t[1]];
        if (l0 <= l[0] && l1 <= l[1])
          ans = min(
              ans, d[i][j] + d[s[0]][i] + d[j][t[0]] + d[s[1]][i] + d[j][t[1]]);
      }
    }
  }
  cout << m - ans << endl;
  return 0;
}
