#include <bits/stdc++.h>
using namespace std;
struct node {
  int v, next;
} edge[6010];
int n, m;
int dis[3010][3010], Head[3010], tot, INF = 1e9;
int s1, s2, t1, t2, d1, d2;
bool vis[3010];
queue<int> qu;
void add(int u, int v) {
  edge[tot].v = v;
  edge[tot].next = Head[u];
  Head[u] = tot++;
}
void debug() {
  int i, j, k;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) printf("%d ", dis[i][j]);
    printf("\n");
  }
}
int main() {
  int i, j, k, u, v, ans;
  scanf("%d%d", &n, &m);
  memset(Head, -1, sizeof(Head));
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  scanf("%d%d%d%d%d%d", &s1, &t1, &d1, &s2, &t2, &d2);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) dis[i][j] = INF;
  for (i = 1; i <= n; i++) {
    memset(vis, 0, sizeof(vis));
    dis[i][i] = 0;
    vis[i] = 1;
    qu.push(i);
    while (!qu.empty()) {
      u = qu.front();
      qu.pop();
      for (j = Head[u]; j != -1; j = edge[j].next) {
        v = edge[j].v;
        if (vis[v]) continue;
        dis[i][v] = dis[i][u] + 1;
        vis[v] = 1;
        qu.push(v);
      }
    }
  }
  if (dis[s1][t1] > d1 || dis[s2][t2] > d2) {
    printf("-1\n");
    return 0;
  }
  ans = dis[s1][t1] + dis[s2][t2];
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= d1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= d2) {
        ans = min(
            ans, dis[s1][i] + dis[s2][i] + dis[i][j] + dis[j][t1] + dis[j][t2]);
      }
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= d1 &&
          dis[t2][i] + dis[i][j] + dis[j][s2] <= d2)
        ans = min(
            ans, dis[s1][i] + dis[t2][i] + dis[i][j] + dis[j][t1] + dis[j][s2]);
    }
  printf("%d\n", m - ans);
}
