#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e3 + 9, MOD = 1e9 + 7;
int n, m;
vector<int> adj[maxN];
int shp[maxN][maxN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  memset(shp, -1, sizeof shp);
  int a, b, l1, c, d, l2;
  cin >> n >> m;
  for (int i = 0, u, v; i < m; i++) {
    cin >> u >> v, u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  cin >> a >> b >> l1 >> c >> d >> l2;
  a--, b--, c--, d--;
  for (int u = 0; u < n; u++) {
    queue<int> q;
    q.push(u);
    shp[u][u] = 0;
    while (q.size()) {
      int cr = q.front();
      q.pop();
      for (int sn : adj[cr]) {
        if (shp[u][sn] == -1) {
          shp[u][sn] = shp[u][cr] + 1;
          q.push(sn);
        }
      }
    }
  }
  if (shp[a][b] > l1 || shp[c][d] > l2) {
    cout << "-1\n";
    return 0;
  }
  int bes = shp[a][b] + shp[c][d];
  for (int u = 0; u < 2; u++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int dst1 = shp[a][i] + shp[i][j] + shp[j][b];
        int dst2 = shp[c][i] + shp[i][j] + shp[j][d];
        if (dst1 <= l1 && dst2 <= l2) {
          bes = min(bes, dst1 + dst2 - shp[i][j]);
        }
      }
    }
    swap(a, b);
  }
  cout << m - bes << '\n';
}
