#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
vector<int> vc[maxn];
int M[maxn][maxn];
bool visit[maxn];
int n, m;
void bfs() {
  int i, j, k;
  int u, v, size;
  queue<int> Q;
  memset(M, 0x1f, sizeof(M));
  for (i = 1; i <= n; ++i) M[i][i] = 0;
  for (i = 1; i <= n; ++i) {
    memset(visit, false, sizeof(visit));
    visit[i] = true;
    Q.push(i);
    while (!Q.empty()) {
      u = Q.front();
      Q.pop();
      size = vc[u].size();
      for (j = 0; j < size; ++j) {
        v = vc[u][j];
        if (!visit[v]) {
          visit[v] = true;
          M[i][v] = M[i][u] + 1;
          Q.push(v);
        }
      }
    }
  }
}
int main() {
  int i, j, k;
  int s1, t1, l1;
  int s2, t2, l2;
  int ans;
  scanf("%d %d", &n, &m);
  for (i = 0; i < m; ++i) {
    scanf("%d %d", &j, &k);
    vc[j].push_back(k);
    vc[k].push_back(j);
  }
  scanf("%d %d %d", &s1, &t1, &l1);
  scanf("%d %d %d", &s2, &t2, &l2);
  bfs();
  if (M[s1][t1] > l1 || M[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  ans = M[s1][t1] + M[s2][t2];
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      if (M[s1][i] + M[i][j] + M[j][t1] <= l1 &&
          M[s2][i] + M[i][j] + M[j][t2] <= l2)
        ans = min(ans, M[s1][i] + M[i][j] + M[j][t1] + M[s2][i] + M[j][t2]);
      if (M[s1][j] + M[i][j] + M[i][t1] <= l1 &&
          M[s2][i] + M[i][j] + M[j][t2] <= l2)
        ans = min(ans, M[s1][j] + M[i][j] + M[i][t1] + M[s2][i] + M[j][t2]);
      if (M[s1][i] + M[i][j] + M[j][t1] <= l1 &&
          M[s2][j] + M[i][j] + M[i][t2] <= l2)
        ans = min(ans, M[s1][i] + M[i][j] + M[j][t1] + M[s2][j] + M[i][t2]);
      if (M[s1][j] + M[i][j] + M[i][t1] <= l1 &&
          M[s2][j] + M[i][j] + M[i][t2] <= l2)
        ans = min(ans, M[s1][j] + M[i][j] + M[i][t1] + M[s2][j] + M[i][t2]);
    }
  }
  printf("%d\n", m - ans);
  return 0;
}
