#include <bits/stdc++.h>
using namespace std;
int dist[3000][3000];
vector<int> G[3000];
int n, m, s1, s2, t1, t2, l1, l2;
int oo = 1 << 28;
void bfs(int s, int *dist) {
  fill(dist, dist + n, oo);
  queue<int> q;
  q.push(s);
  dist[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : G[u])
      if (dist[v] == oo) {
        dist[v] = dist[u] + 1;
        q.push(v);
      }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (m); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  scanf("%d %d %d", &s1, &t1, &l1);
  s1--, t1--;
  scanf("%d %d %d", &s2, &t2, &l2);
  s2--, t2--;
  for (int i = 0; i < (n); i++) bfs(i, dist[i]);
  int ans = -1;
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (n); j++) {
      int d1 = dist[s1][i] + dist[i][j] + dist[j][t1];
      int d2 = dist[s2][i] + dist[i][j] + dist[j][t2];
      int l = d1 + d2 - dist[i][j];
      if (d1 <= l1 && d2 <= l2 && l <= m) ans = max(ans, m - l);
      d2 = dist[s2][j] + dist[i][j] + dist[i][t2];
      l = d1 + d2 - dist[i][j];
      if (d1 <= l1 && d2 <= l2 && l <= m) ans = max(ans, m - l);
    }
  if (dist[s1][t1] <= l1 && dist[s2][t2] <= l2 &&
      dist[s1][t1] + dist[s2][t2] <= m)
    ans = max(ans, m - dist[s1][t1] - dist[s2][t2]);
  cerr << ans << endl;
  cout << ans << endl;
  return 0;
}
