#include <bits/stdc++.h>
using namespace std;
bool debug;
const int inf = 1e9 + 5;
const int nax = 3005;
vector<int> w[nax];
int d[nax][nax];
int main(int argc, char *argv[]) {
  debug = argc > 1;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int _ = 0; _ <= (m)-1; ++_) {
    int a, b;
    scanf("%d%d", &a, &b);
    w[a].push_back(b);
    w[b].push_back(a);
  }
  for (int i = 1; i <= (n); ++i) {
    for (int j = 1; j <= (n); ++j) d[i][j] = inf;
    d[i][i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int a = q.front();
      q.pop();
      for (int b : w[a])
        if (d[i][b] == inf) {
          d[i][b] = d[i][a] + 1;
          q.push(b);
        }
    }
  }
  int a[2], b[2], lim[2];
  for (int r = 0; r <= (2) - 1; ++r) scanf("%d%d%d", &a[r], &b[r], &lim[r]);
  int res = inf;
  for (int i = 1; i <= (n); ++i)
    for (int j = 1; j <= (n); ++j)
      for (int _ = 0; _ <= (2) - 1; ++_) {
        int dist[2];
        for (int r = 0; r <= (2) - 1; ++r)
          dist[r] = d[a[r]][i] + d[i][j] + d[j][b[r]];
        if (dist[0] <= lim[0] && dist[1] <= lim[1])
          res = min(res, dist[0] + dist[1] - d[i][j]);
        swap(a[0], b[0]);
      }
  int dist[2];
  for (int r = 0; r <= (2) - 1; ++r) dist[r] = d[a[r]][b[r]];
  if (dist[0] <= lim[0] && dist[1] <= lim[1]) res = min(res, dist[0] + dist[1]);
  printf("%d\n", res == inf ? -1 : m - res);
  return 0;
}
