#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, dist[3000 + 5][3000 + 5], parent[3000 + 5][3000 + 5];
int s0, t0, i0, s1, t1, i1;
vector<vector<int> > edges;
map<pair<int, int>, bool> allEdges;
set<pair<int, int> > impEdges;
void bfs(int strt) {
  queue<int> Q;
  dist[strt][strt] = 0;
  Q.push(strt);
  parent[strt][strt] = -1;
  while (!Q.empty()) {
    int curr = Q.front();
    Q.pop();
    for (int i = 0; i < edges[curr].size(); i++) {
      int neigh = edges[curr][i];
      if (dist[strt][neigh] == 0 && neigh != strt) {
        dist[strt][neigh] = dist[strt][curr] + 1;
        parent[strt][neigh] = curr;
        Q.push(neigh);
      }
    }
  }
}
int main() {
  cin >> n >> m;
  edges.assign(n + 5, vector<int>());
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    edges[a].push_back(b);
    edges[b].push_back(a);
    allEdges[pair<int, int>(a, b)] = 1;
  }
  cin >> s0 >> t0 >> i0;
  cin >> s1 >> t1 >> i1;
  for (int i = 1; i <= n; i++) {
    bfs(i);
  }
  if ((dist[s0][t0] > i0 && dist[t0][s0] > i0) ||
      (dist[s1][t1] > i1 && dist[t1][s1] > i1)) {
    cout << -1 << endl;
    return 0;
  }
  int ans = dist[s0][t0] + dist[s1][t1];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int d1 = dist[i][j],
          d2 = min(dist[s0][i] + dist[j][t0], dist[s0][j] + dist[i][t0]),
          d3 = min(dist[s1][i] + dist[j][t1], dist[s1][j] + dist[i][t1]);
      if (d1 + d2 <= i0 && d1 + d3 <= i1) ans = min(ans, d1 + d2 + d3);
    }
  }
  printf("%d\n", m - ans);
}
