#include <bits/stdc++.h>
using namespace std;
const long long INF = 1E9 + 9;
const int maxn = 3009;
int dis[maxn][maxn];
int head[maxn], cnt;
bool visit[maxn];
struct node {
  int v, next;
} List[maxn << 1];
void add(int u, int v) {
  List[cnt].v = v;
  List[cnt].next = head[u];
  head[u] = cnt++;
}
int main() {
  int i, j, n, m, x1, y1, x2, y2, t1, t2, u, v;
  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);
  }
  for (i = 1; i <= n; i++) {
    queue<int> q;
    memset(visit, 0, sizeof(visit));
    dis[i][i] = 0;
    q.push(i);
    visit[i] = true;
    while (!q.empty()) {
      u = q.front();
      q.pop();
      for (int j = head[u]; ~j; j = List[j].next)
        if (!visit[List[j].v]) {
          visit[List[j].v] = true;
          dis[i][List[j].v] = dis[i][u] + 1;
          q.push(List[j].v);
        }
    }
  }
  scanf("%d%d%d", &x1, &y1, &t1);
  scanf("%d%d%d", &x2, &y2, &t2);
  if (dis[x1][y1] > t1 || dis[x2][y2] > t2) {
    printf("-1\n");
    return 0;
  }
  int Min = dis[x1][y1] + dis[x2][y2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dis[x1][i] + dis[i][j] + dis[j][y1] <= t1 &&
          dis[x2][i] + dis[i][j] + dis[j][y2] <= t2)
        Min = min(
            Min, dis[x1][i] + dis[i][j] + dis[j][y1] + dis[x2][i] + dis[j][y2]);
      if (dis[x1][i] + dis[i][j] + dis[j][y1] <= t1 &&
          dis[y2][i] + dis[i][j] + dis[j][x2] <= t2)
        Min = min(
            Min, dis[x1][i] + dis[i][j] + dis[j][y1] + dis[y2][i] + dis[j][x2]);
    }
  }
  printf("%d\n", m - Min);
  return 0;
}
