#include <bits/stdc++.h>
using namespace ::std;
const int N = 3000 + 5;
vector<int> g[N];
int d[N][N];
int main() {
  int n, m;
  int i, j, k;
  cin >> n >> m;
  memset(d, -1, sizeof d);
  for (i = 0; i < m; i++) {
    cin >> j >> k;
    g[j - 1].push_back(k - 1);
    g[k - 1].push_back(j - 1);
  }
  for (i = 0; i < n; i++) {
    queue<int> q;
    q.push(i);
    d[i][i] = 0;
    while (!q.empty()) {
      j = q.front();
      q.pop();
      for (k = 0; k < g[j].size(); k++) {
        if (d[i][g[j][k]] == -1) {
          d[i][g[j][k]] = d[i][j] + 1;
          q.push(g[j][k]);
        }
      }
    }
  }
  int s[2], t[2];
  int l1, l2;
  cin >> s[0] >> t[0] >> l1;
  cin >> s[1] >> t[1] >> l2;
  s[0]--;
  t[0]--;
  s[1]--;
  t[1]--;
  int ans = m + 1;
  for (int it = 0; it < 2; it++) {
    swap(s[0], t[0]);
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        int v[] = {d[s[0]][i] + d[i][j] + d[j][t[0]],
                   d[s[1]][i] + d[i][j] + d[j][t[1]]};
        if (v[0] <= l1 && v[1] <= l2) ans = min(ans, v[0] + v[1] - d[i][j]);
      }
    }
  }
  if (d[s[0]][t[0]] <= l1 && d[s[1]][t[1]] <= l2)
    ans = min(ans, d[s[0]][t[0]] + d[s[1]][t[1]]);
  if (ans > m)
    cout << "-1";
  else
    cout << m - ans;
}
