#include <bits/stdc++.h>
using namespace std;
const int L = 3010;
const int INF = 1000111222;
vector<int> g[L];
int n, m, s1, t1, l1, s2, t2, l2;
int path[L][L];
void bfs(int start) {
  queue<int> q;
  path[start][start] = 0;
  q.push(start);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto u : g[v]) {
      if (path[start][v] + 1 < path[start][u]) {
        path[start][u] = path[start][v] + 1;
        q.push(u);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  int x, y;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  s1--;
  t1--;
  s2--;
  t2--;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) path[i][j] = INF;
  for (int i = 0; i < n; i++) {
    bfs(i);
  }
  int ans = INF;
  if (path[s1][t1] <= l1 && path[s2][t2] <= l2)
    ans = path[s1][t1] + path[s2][t2];
  for (int v1 = 0; v1 < n; v1++) {
    for (int v2 = 0; v2 < n; v2++) {
      int m1 = min(path[s1][v1] + path[v2][t1], path[s1][v2] + path[v1][t1]);
      int m2 = min(path[s2][v1] + path[v2][t2], path[s2][v2] + path[v1][t2]);
      if (m1 + path[v1][v2] > l1 || m2 + path[v1][v2] > l2) continue;
      ans = min(ans, path[v1][v2] + m1 + m2);
    }
  }
  if (ans == INF) {
    ans = m + 1;
  }
  cout << m - ans;
}
