#include <bits/stdc++.h>
using namespace std;
int d[3005][3005], viz[3005];
vector<int> v[3005];
int n;
queue<int> q;
void bfs(int nod) {
  for (int i = 1; i <= n; ++i) viz[i] = 0;
  q.empty();
  q.push(nod);
  viz[nod] = 1;
  while (!q.empty()) {
    int x = q.front();
    for (int i = 0; i < v[x].size(); ++i) {
      if (viz[v[x][i]] == 0) {
        viz[v[x][i]] = 1;
        q.push(v[x][i]);
        d[nod][v[x][i]] = d[nod][x] + 1;
      }
    }
    q.pop();
  }
}
int main() {
  int m, a, b, s1, t1, l1, s2, t2, l2;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for (int i = 1; i <= n; ++i) bfs(i);
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  if (d[s1][t1] > l1) {
    cout << -1;
    return 0;
  }
  if (d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  int ans = m - (d[s1][t1] + d[s2][t2]);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2)
        ans =
            max(ans, m - (d[s1][i] + d[i][j] + d[j][t1] + d[s2][i] + d[j][t2]));
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][j] + d[i][j] + d[i][t2] <= l2)
        ans =
            max(ans, m - (d[s1][i] + d[i][j] + d[j][t1] + d[s2][j] + d[i][t2]));
    }
  cout << ans;
}
