#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
bool vis[maxn];
int n, m, u, v, s1, t1, l1, s2, t2, l2, tmp, ans;
int d[maxn][maxn];
vector<int> G[maxn];
void bfs(int s) {
  queue<int> q;
  q.push(s);
  vis[s] = true;
  d[s][s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (vis[v] == true) {
        continue;
      }
      d[s][v] = d[s][u] + 1;
      q.push(v);
      vis[v] = true;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  for (int i = 1; i <= n; i++) {
    memset(vis, 0, sizeof(vis));
    bfs(i);
  }
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  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] > l1) {
        continue;
      }
      tmp = d[i][j] + d[s1][i] + d[j][t1];
      if (d[s2][i] + d[i][j] + d[j][t2] <= l2) {
        ans = min(ans, tmp + d[s2][i] + d[j][t2]);
      }
      if (d[s2][j] + d[i][j] + d[i][t2] <= l2) {
        ans = min(ans, tmp + d[s2][j] + d[i][t2]);
      }
    }
  }
  printf("%d\n", m - ans);
  return 0;
}
