#include <bits/stdc++.h>
using namespace std;
int F[3003][3003], vis[3003], a, b, c, x, y, z, n, m, t;
vector<int> D[3003];
void BFS(int K) {
  queue<int> q;
  for (int i = 1; i <= n; i++) vis[i] = 0, F[K][i] = 1e9;
  vis[K] = 1;
  q.push(K);
  F[K][K] = 0;
  while (!q.empty()) {
    int h = q.front();
    q.pop();
    for (int i = 0; i < D[h].size(); i++) {
      int now = D[h][i];
      if (!vis[now]) {
        F[K][now] = F[K][h] + 1;
        q.push(now);
        vis[now] = 1;
      }
    }
  }
}
int main() {
  int m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int v, u;
    cin >> v >> u;
    D[v].push_back(u);
    D[u].push_back(v);
  }
  for (int i = 1; i <= n; i++) BFS(i);
  cin >> a >> b >> c >> x >> y >> z;
  if (F[a][b] > c || F[x][y] > z) return puts("-1"), 0;
  int t = F[a][b] + F[x][y];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int F1 = F[a][i] + F[i][j] + F[j][b], F2 = F[x][i] + F[i][j] + F[j][y];
      F2 = min(F2, F[x][j] + F[i][j] + F[i][y]);
      if (F1 <= c && F2 <= z) t = min(t, F1 + F2 - F[i][j]);
    }
  cout << m - t;
}
