#include <bits/stdc++.h>
using namespace std;
const int maxn = 3000 + 7;
const int INF = 0x3f3f3f3f;
int dis[maxn][maxn], vis[maxn];
vector<int> G[maxn];
void bfs(int s) {
  memset(vis, 0, sizeof(vis));
  queue<int> q;
  q.push(s);
  vis[s] = 1;
  dis[s][s] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < G[x].size(); i++) {
      int v = G[x][i];
      if (vis[v]) continue;
      vis[v] = 1;
      dis[s][v] = dis[s][x] + 1;
      q.push(v);
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= n; i++) {
    bfs(i);
  }
  int s1, t1, l1;
  scanf("%d%d%d", &s1, &t1, &l1);
  int s2, t2, l2;
  scanf("%d%d%d", &s2, &t2, &l2);
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int ans = dis[s1][t1] + dis[s2][t2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dis[s1][i] == INF || dis[i][j] == INF || dis[j][t1] == INF) continue;
      if (dis[s2][i] == INF || dis[i][j] == INF || dis[j][t2] == INF) continue;
      int d1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      int d2 = dis[s2][i] + dis[i][j] + dis[j][t2];
      if (d1 > l1 || d2 > l2) continue;
      ans = min(ans, d1 + d2 - dis[i][j]);
    }
  }
  swap(s2, t2);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dis[s1][i] == INF || dis[i][j] == INF || dis[j][t1] == INF) continue;
      if (dis[s2][i] == INF || dis[i][j] == INF || dis[j][t2] == INF) continue;
      int d1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      int d2 = dis[s2][i] + dis[i][j] + dis[j][t2];
      if (d1 > l1 || d2 > l2) continue;
      ans = min(ans, d1 + d2 - dis[i][j]);
    }
  }
  printf("%d\n", m - ans);
  return 0;
}
