#include <bits/stdc++.h>
using namespace std;
struct node1 {
  int v;
  int w;
  int next;
};
struct node2 {
  bool friend operator<(node2 n1, node2 n2) { return n1.w > n2.w; }
  int v;
  int w;
};
node1 edge[1000000];
priority_queue<node2> que;
int dis[3010][3010];
int first[3010], book[3010];
int n, m, num;
int s1, t1, l1, s2, t2, l2;
void addedge(int u, int v, int w) {
  edge[num].v = v;
  edge[num].w = w;
  edge[num].next = first[u];
  first[u] = num++;
  return;
}
void dijkstra() {
  node2 cur, tem;
  int i, j, u, v, w;
  memset(dis, 0x3f, sizeof(dis));
  for (i = 1; i <= n; i++) {
    while (!que.empty()) que.pop();
    memset(book, 0, sizeof(book));
    tem.v = i, tem.w = 0;
    que.push(tem);
    dis[i][i] = 0;
    while (!que.empty()) {
      cur = que.top();
      que.pop();
      u = cur.v;
      if (book[u]) continue;
      book[u] = 1;
      for (j = first[u]; j != -1; j = edge[j].next) {
        v = edge[j].v, w = edge[j].w;
        if (!book[v] && dis[i][v] > dis[i][u] + w) {
          dis[i][v] = dis[i][u] + w;
          tem.v = v, tem.w = dis[i][v];
          que.push(tem);
        }
      }
    }
  }
  return;
}
int main() {
  int i, j, u, v, ans;
  while (scanf("%d%d", &n, &m) != EOF) {
    memset(first, -1, sizeof(first));
    num = 0;
    for (i = 1; i <= m; i++) {
      scanf("%d%d", &u, &v);
      addedge(u, v, 1);
      addedge(v, u, 1);
    }
    scanf("%d%d%d", &s1, &t1, &l1);
    scanf("%d%d%d", &s2, &t2, &l2);
    dijkstra();
    if (!(dis[s1][t1] <= l1 && dis[s2][t2] <= l2)) {
      printf("-1\n");
      continue;
    }
    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] <= l1 &&
            dis[s2][i] + dis[i][j] + dis[j][t2] <= l2) {
          ans = min(ans, dis[s1][i] + dis[j][t1] + dis[s2][i] + dis[j][t2] +
                             dis[i][j]);
        }
        if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
            dis[t2][i] + dis[i][j] + dis[j][s2] <= l2) {
          ans = min(ans, dis[s1][i] + dis[j][t1] + dis[t2][i] + dis[j][s2] +
                             dis[i][j]);
        }
        if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1 &&
            dis[s2][i] + dis[i][j] + dis[j][t2] <= l2) {
          ans = min(ans, dis[t1][i] + dis[j][s1] + dis[s2][i] + dis[j][t2] +
                             dis[i][j]);
        }
        if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1 &&
            dis[t2][i] + dis[i][j] + dis[j][s2] <= l2) {
          ans = min(ans, dis[t1][i] + dis[j][s1] + dis[t2][i] + dis[j][s2] +
                             dis[i][j]);
        }
      }
    }
    printf("%d\n", m - ans);
  }
  return 0;
}
