#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, i, u, v;
  cin >> n >> m;
  vector<int> a[n + 1];
  for (i = 0; i < m; i++) {
    cin >> u >> v;
    a[u].push_back(v);
    a[v].push_back(u);
  }
  int d[n + 1][n + 1];
  memset(d, -1, sizeof d);
  for (i = 1; i <= n; i++) {
    d[i][i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int j = 0; j < a[u].size(); j++) {
        int ins = a[u][j];
        if (d[i][ins] == -1) {
          d[i][ins] = d[i][u] + 1;
          q.push(ins);
        }
      }
    }
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  int ans = m + 1;
  for (i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int p1 = d[s1][i] + d[t1][j] + d[i][j];
      int p2 = d[s2][i] + d[t2][j] + d[i][j];
      if (p1 <= l1 && p2 <= l2) {
        ans = min(ans, p1 + p2 - d[i][j]);
      }
    }
  }
  if (d[s1][t1] <= l1 && d[s2][t2] <= l2) {
    ans = min(ans, d[s1][t1] + d[s2][t2]);
  }
  swap(s1, t1);
  for (i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int p1 = d[s1][i] + d[t1][j] + d[i][j];
      int p2 = d[s2][i] + d[t2][j] + d[i][j];
      if (p1 <= l1 && p2 <= l2) {
        ans = min(ans, p1 + p2 - d[i][j]);
      }
    }
  }
  if (ans > m)
    cout << "-1" << endl;
  else {
    cout << m - ans << endl;
  }
}
