#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30) - 1;
const int mod = 1000000007;
const int maxn = 5005;
int n, m;
vector<int> e[maxn];
int vis[maxn];
int d[maxn][maxn];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  int s1, t1, d1, s2, t2, d2;
  scanf("%d %d %d %d %d %d", &s1, &t1, &d1, &s2, &t2, &d2);
  for (int i = 1; i <= n; i++) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    vis[i] = 1;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int j = 0; j < e[u].size(); j++) {
        int v = e[u][j];
        if (vis[v]) continue;
        vis[v] = 1;
        d[i][v] = d[i][u] + 1;
        q.push(v);
      }
    }
  }
  if (d[s1][t1] > d1 || d[s2][t2] > d2) {
    puts("-1");
    return 0;
  }
  int ans = d[s1][t1] + d[s2][t2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[s1][i] + d[i][j] + d[j][t1] <= d1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= d2)
        ans = min(ans, d[s1][i] + d[i][j] + d[j][t1] + d[s2][i] + d[j][t2]);
      if (d[s1][i] + d[i][j] + d[j][t1] <= d1 &&
          d[t2][i] + d[i][j] + d[j][s2] <= d2)
        ans = min(ans, d[s1][i] + d[i][j] + d[j][t1] + d[t2][i] + d[j][s2]);
    }
  }
  printf("%d\n", m - ans);
  return 0;
}
