#include <bits/stdc++.h>
using namespace std;
const int maxn = 3000 + 10;
vector<int> pic[maxn];
int path[maxn][maxn];
queue<int> q;
void bfs(int s) {
  path[s][s] = 0;
  while (!q.empty()) q.pop();
  q.push(s);
  while (!q.empty()) {
    int thi = q.front();
    for (int i = 0; i < pic[thi].size(); i++) {
      int x = pic[thi][i];
      if (path[s][x] != -1) continue;
      path[s][x] = path[s][thi] + 1;
      q.push(x);
    }
    q.pop();
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    pic[x].push_back(y);
    pic[y].push_back(x);
  }
  memset(path, -1, sizeof(path));
  for (int i = 1; i <= n; i++) bfs(i);
  int s1, t1, l1, s2, t2, l2;
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  if (path[s1][t1] > l1 || path[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int ans = path[s1][t1] + path[s2][t2];
  for (int d1 = 1; d1 <= n; d1++)
    for (int d2 = 1; d2 <= n; d2++) {
      if (path[s1][d1] + path[d1][d2] + path[d2][t1] > l1) continue;
      if (path[s2][d1] + path[d1][d2] + path[d2][t2] <= l2)
        ans = min(ans, path[s1][d1] + path[s2][d1] + path[d1][d2] +
                           path[d2][t1] + path[d2][t2]);
      if (path[s2][d2] + path[d2][d1] + path[d1][t2] <= l2)
        ans = min(ans, path[s1][d1] + path[s2][d2] + path[d1][d2] +
                           path[d2][t1] + path[d1][t2]);
    }
  printf("%d\n", m - ans);
  return 0;
}
