#include <bits/stdc++.h>
using namespace std;
vector<int> g[3005];
vector<vector<int>> d(3005, vector<int>(3005, 0));
vector<int> bfs(3005, 0);
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    int x = 0;
    bfs[x++] = i;
    d[i][i] = 1;
    for (int j = 0; j < x; j++) {
      for (int k = 0; k < g[bfs[j]].size(); k++) {
        if (!d[i][g[bfs[j]][k]]) {
          d[i][g[bfs[j]][k]] = d[i][bfs[j]] + 1;
          bfs[x++] = g[bfs[j]][k];
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      d[i][j]--;
    }
  }
  int a1, b1, a2, b2, t1, t2;
  cin >> a1 >> b1 >> t1 >> a2 >> b2 >> t2;
  int cnt = d[a1][b1] + d[a2][b2];
  if (cnt > t1 + t2) {
    cout << -1 << endl;
  } else {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int da1b1 = d[a1][i] + d[i][j] + d[j][b1];
        if (da1b1 <= t1) {
          int da2b2 = d[a2][i] + d[i][j] + d[j][b2];
          if (da2b2 <= t2) {
            cnt = min(cnt, da1b1 + da2b2 - d[i][j]);
          }
          int db2a2 = d[b2][i] + d[i][j] + d[j][a2];
          if (db2a2 <= t2) {
            cnt = min(cnt, da1b1 + db2a2 - d[i][j]);
          }
        }
      }
    }
    cout << m - cnt << endl;
  }
  return 0;
}
