#include <bits/stdc++.h>
using namespace std;
int rint() {
  int x;
  scanf("%d", &x);
  return x;
}
vector<int> G[3000];
int dist[3000][3000], inq[3000], n, m;
void bfs(int u) {
  for (int i = (0); i < (n); ++i) inq[i] = 0;
  queue<pair<int, int> > q;
  q.push(pair<int, int>(0, u));
  inq[u] = 1;
  while (!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    dist[u][p.second] = p.first;
    for (int i = (0); i < (G[p.second].size()); ++i) {
      int v = G[p.second][i];
      if (!inq[v]) {
        q.push(pair<int, int>(p.first + 1, v));
        inq[v] = 1;
      }
    }
  }
}
int main() {
  n = rint(), m = rint();
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) dist[i][j] = -1;
  for (int i = (0); i < (m); ++i) {
    int u = rint() - 1, v = rint() - 1;
    G[u].push_back(v);
    G[v].push_back(u);
    dist[u][v] = dist[v][u] = 1;
  }
  for (int i = (0); i < (n); ++i) bfs(i);
  int s1 = rint() - 1, t1 = rint() - 1, l1 = rint();
  int s2 = rint() - 1, t2 = rint() - 1, l2 = rint();
  int ans = -1;
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) {
      if (dist[s1][i] == -1 || dist[s2][i] == -1 || dist[j][t1] == -1 ||
          dist[j][t2] == -1 || dist[i][j] == -1)
        continue;
      if (dist[s1][i] + dist[i][j] + dist[j][t1] <= l1 &&
          dist[s2][i] + dist[i][j] + dist[j][t2] <= l2) {
        int len =
            dist[s1][i] + dist[s2][i] + dist[i][j] + dist[j][t1] + dist[j][t2];
        ans = max(ans, m - len);
      }
      if (dist[s1][j] == -1 || dist[s2][i] == -1 || dist[i][t1] == -1 ||
          dist[j][t2] == -1 || dist[i][j] == -1)
        continue;
      if (dist[s1][j] + dist[i][j] + dist[i][t1] <= l1 &&
          dist[s2][i] + dist[i][j] + dist[j][t2] <= l2) {
        int len =
            dist[s1][j] + dist[s2][i] + dist[i][j] + dist[i][t1] + dist[j][t2];
        ans = max(ans, m - len);
      }
    }
  if (dist[s1][t1] <= l1 && dist[s2][t2] <= l2) {
    ans = max(ans, m - (dist[s1][t1] + dist[s2][t2]));
  }
  printf("%d\n", ans);
  return 0;
}
