#include <bits/stdc++.h>
using namespace std;
vector<int> e[3333];
int d[3333][3333];
int n, m;
queue<int> q;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int first, second;
    scanf("%d%d", &first, &second);
    --first;
    --second;
    e[first].push_back(second);
    e[second].push_back(first);
  }
  for (int i = 0; i < n; ++i) {
    q.push(i);
    memset(d[i], -1, sizeof(d[i]));
    d[i][i] = 0;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int j = 0; j < (int)(e[cur]).size(); ++j) {
        if (d[i][e[cur][j]] == -1) {
          d[i][e[cur][j]] = d[i][cur] + 1;
          q.push(e[cur][j]);
        }
      }
    }
  }
  int s1, t1, l1, s2, l2, t2;
  scanf("%d%d%d", &s1, &t1, &l1);
  --s1;
  --t1;
  scanf("%d%d%d", &s2, &t2, &l2);
  --s2;
  --t2;
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int left = d[s1][t1] + d[s2][t2];
  for (int a = 0; a < n; ++a) {
    for (int b = 0; b < n; ++b) {
      if (d[s1][a] + d[a][b] + d[b][t1] <= l1 &&
          d[s2][a] + d[a][b] + d[b][t2] <= l2) {
        left = min(left, d[a][b] + d[s1][a] + d[b][t1] + d[s2][a] + d[b][t2]);
      }
      if (d[s1][a] + d[a][b] + d[b][t1] <= l1 &&
          d[t2][a] + d[a][b] + d[b][s2] <= l2) {
        left = min(left, d[a][b] + d[s1][a] + d[b][t1] + d[s2][b] + d[a][t2]);
      }
    }
  }
  printf("%d\n", m - left);
}
