#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
int st[3], en[3], t[3], cnt;
int dist[3010][3010];
int head[3010], vis[3010];
int n, m, x, y, z, len, flag;
struct Edge {
  int u;
  int next;
} e[2 * 3010];
void Add_Edge(int u, int v) {
  e[cnt].u = u;
  e[cnt].next = head[v];
  head[v] = cnt++;
}
void bfs() {
  for (int i = 1; i <= n; i++) {
    dist[i][i] = 0;
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(i);
    vis[i] = 1;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int j = head[cur]; j != -1; j = e[j].next) {
        int v = e[j].u;
        if (vis[v]) continue;
        int next = v;
        dist[i][v] = dist[i][cur] + 1;
        q.push(next);
        vis[v] = 1;
      }
    }
  }
}
int main() {
  while (~scanf("%d%d", &n, &m)) {
    flag = 0, len = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) dist[i][j] = INF;
    for (int i = 0; i < m; i++) {
      scanf("%d%d", &x, &y);
      Add_Edge(x, y);
      Add_Edge(y, x);
    }
    bfs();
    for (int i = 1; i <= 2; i++) {
      scanf("%d%d%d", &st[i], &en[i], &t[i]);
      if (t[i] < dist[st[i]][en[i]]) flag = 1;
      len += dist[st[i]][en[i]];
    }
    if (flag) {
      printf("-1\n");
      continue;
    }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        int l1 = dist[st[1]][i] + dist[i][j] + dist[j][en[1]];
        int l2 = dist[st[2]][i] + dist[i][j] + dist[j][en[2]];
        int l3 = dist[en[2]][i] + dist[i][j] + dist[j][st[2]];
        if (l1 <= t[1] && l2 <= t[2]) len = min(len, l1 + l2 - dist[i][j]);
        if (l1 <= t[1] && l3 <= t[2]) len = min(len, l1 + l3 - dist[i][j]);
      }
    printf("%d\n", m - len);
  }
  return 0;
}
