#include <bits/stdc++.h>
using namespace std;
int n, m;
int s[4], l1, l2;
int d[3100][3100];
vector<int> g[3100];
void bfs() {
  int x, y;
  for (int k = 1; k <= n; ++k) {
    queue<int> q;
    memset(d[k], 0x3F3F3F3F, sizeof d[k]);
    q.push(k);
    d[k][k] = 0;
    while (!q.empty()) {
      x = q.front();
      q.pop();
      for (int i = 0; i < (int)g[x].size(); ++i) {
        y = g[x][i];
        if (d[k][y] == 0x3F3F3F3F) {
          d[k][y] = d[k][x] + 1;
          q.push(y);
        }
      }
    }
  }
}
int main() {
  int x, y, ans = 0x3F3F3F3F, aux;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  scanf("%d %d %d", &s[0], &s[1], &l1);
  scanf("%d %d %d", &s[2], &s[3], &l2);
  bfs();
  if (d[s[0]][s[1]] <= l1 && d[s[2]][s[3]] <= l2) {
    ans = m - (d[s[0]][s[1]]) - (d[s[2]][s[3]]);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      aux = m - d[i][j] - d[s[0]][i] - d[j][s[1]] - d[s[2]][i] - d[j][s[3]];
      if (d[s[0]][i] + d[i][j] + d[j][s[1]] <= l1 &&
          d[s[2]][i] + d[i][j] + d[j][s[3]] <= l2)
        ans = max(ans, aux);
      swap(s[0], s[1]);
      aux = m - d[i][j] - d[s[0]][i] - d[j][s[1]] - d[s[2]][i] - d[j][s[3]];
      if (d[s[0]][i] + d[i][j] + d[j][s[1]] <= l1 &&
          d[s[2]][i] + d[i][j] + d[j][s[3]] <= l2)
        ans = max(ans, aux);
      swap(s[2], s[3]);
      aux = m - d[i][j] - d[s[0]][i] - d[j][s[1]] - d[s[2]][i] - d[j][s[3]];
      if (d[s[0]][i] + d[i][j] + d[j][s[1]] <= l1 &&
          d[s[2]][i] + d[i][j] + d[j][s[3]] <= l2)
        ans = max(ans, aux);
      swap(s[0], s[1]);
      aux = m - d[i][j] - d[s[0]][i] - d[j][s[1]] - d[s[2]][i] - d[j][s[3]];
      if (d[s[0]][i] + d[i][j] + d[j][s[1]] <= l1 &&
          d[s[2]][i] + d[i][j] + d[j][s[3]] <= l2)
        ans = max(ans, aux);
    }
  }
  if (ans == 0x3F3F3F3F)
    printf("-1\n");
  else
    printf("%d\n", ans);
  return 0;
}
