#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int dp[3001];
int p[3001][3001];
vector<int> g[3001];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int s[2], t[2], l[2];
  for (int i = 0; i < 2; i++) scanf("%d%d%d", &s[i], &t[i], &l[i]);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) dp[j] = -1;
    q.push(i);
    dp[i] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int j = 0; j < g[u].size(); j++) {
        int v = g[u][j];
        if (dp[v] == -1) {
          dp[v] = dp[u] + 1;
          q.push(v);
        } else if (dp[v] > dp[u] + 1) {
          dp[v] = dp[u] + 1;
          q.push(v);
        }
      }
    }
    for (int j = 1; j <= n; j++) {
      p[i][j] = dp[j];
    }
  }
  int ans = 1000000000;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int tmp1 = p[s[0]][i] + p[i][j] + p[j][t[0]];
      int tmp2 = p[t[0]][i] + p[i][j] + p[j][s[0]];
      int tmp3 = p[s[1]][i] + p[i][j] + p[j][t[1]];
      int tmp4 = p[t[1]][i] + p[i][j] + p[j][s[1]];
      if (tmp1 <= l[0] && tmp3 <= l[1] && ans > tmp1 + tmp3 - p[i][j])
        ans = tmp1 + tmp3 - p[i][j];
      if (tmp1 <= l[0] && tmp4 <= l[1] && ans > tmp1 + tmp4 - p[i][j])
        ans = tmp1 + tmp4 - p[i][j];
      if (tmp2 <= l[0] && tmp3 <= l[1] && ans > tmp2 + tmp3 - p[i][j])
        ans = tmp2 + tmp3 - p[i][j];
      if (tmp2 <= l[0] && tmp4 <= l[1] && ans > tmp2 + tmp4 - p[i][j])
        ans = tmp2 + tmp4 - p[i][j];
    }
  }
  if (p[s[0]][t[0]] <= l[0] && p[s[1]][t[1]] <= l[1] &&
      ans > p[s[0]][t[0]] + p[s[1]][t[1]])
    ans = p[s[0]][t[0]] + p[s[1]][t[1]];
  if (ans > m)
    ans = -1;
  else
    ans = m - ans;
  printf("%d\n", ans);
}
