#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1000 + 5;
int n, m, s1, t1, s2, t2, l1, l2, d[N][N], mxCmn = 0;
vector<int> g[N];
int main() {
  int v, u, i, j;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d %d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  scanf("%d %d %d %d %d %d", &s1, &t1, &l1, &s2, &t2, &l2);
  queue<int> q;
  for (i = 1; i <= n; i++) {
    while (!q.empty()) {
      q.pop();
    }
    for (j = 1; j <= n; j++) {
      d[i][j] = N;
    }
    d[i][i] = 0;
    q.push(i);
    while (!q.empty()) {
      v = q.front();
      for (j = 0; j < (int(g[v].size())); j++) {
        u = g[v][j];
        if (d[i][v] + 1 < d[i][u]) {
          d[i][u] = d[i][v] + 1;
          q.push(u);
        }
      }
      q.pop();
    }
  }
  if ((d[s1][t1] > l1) || (d[s2][t2] > l2)) {
    puts("-1");
    return 0;
  }
  int ans = m - (d[s1][t1] + d[s2][t2]);
  int d1, d2;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      d1 = d[s1][i] + d[i][j] + d[j][t1];
      d2 = d[s2][i] + d[i][j] + d[j][t2];
      if ((d1 <= l1) && (d2 <= l2)) {
        ans = max(ans, m - (d1 + d2 - d[i][j]));
      }
      d1 = d[t1][i] + d[i][j] + d[j][s1];
      d2 = d[s2][i] + d[i][j] + d[j][t2];
      if ((d1 <= l1) && (d2 <= l2)) {
        ans = max(ans, m - (d1 + d2 - d[i][j]));
      }
    }
  }
  printf("%d", ans);
  return 0;
}
