#include <bits/stdc++.h>
using namespace std;
vector<int> g[3005];
bool visit[3005];
int dist[3005][3005];
int main() {
  int n, m, s1, t1, s2, t2, l1, l2;
  cin >> n >> m;
  int a, b;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  memset(dist, 0, sizeof dist);
  for (int i = 1; i <= n; i++) {
    queue<int> q;
    q.push(i);
    memset(visit, 0, sizeof visit);
    visit[i] = 1;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      int len;
      len = g[u].size();
      for (int j = 0; j < len; j++) {
        int v = g[u][j];
        if (visit[v] == 0) {
          visit[v] = 1;
          dist[i][v] = dist[i][u] + 1;
          q.push(v);
        }
      }
    }
  }
  int ans = -1;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  for (int k = 0; k < 2; k++) {
    swap(s1, t1);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int st1 = dist[s1][i] + dist[i][j] + dist[j][t1];
        int st2 = dist[s2][i] + dist[i][j] + dist[j][t2];
        if (st1 <= l1 && st2 <= l2) {
          ans = max(ans, m - (st1 + st2 - dist[i][j]));
        }
      }
    }
  }
  if (dist[s1][t1] <= l1 && dist[s2][t2] <= l2)
    ans = max(ans, m - dist[s1][t1] - dist[s2][t2]);
  cout << ans;
  return 0;
}
