#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
vector<int> e[maxn];
int n, m, s1, t1, l1, s2, t2, l2;
int dis[maxn][maxn];
void addedge(int x, int y) {
  e[x].push_back(y);
  e[y].push_back(x);
}
queue<int> q;
int main() {
  memset(dis, 0x3f, sizeof dis);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    addedge(a, b);
  }
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  for (int i = 1; i <= n; i++) {
    q.push(i);
    dis[i][i] = 0;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int j = 0; j < e[x].size(); j++) {
        int to = e[x][j];
        if (dis[i][x] + 1 < dis[i][to]) dis[i][to] = dis[i][x] + 1, q.push(to);
      }
    }
  }
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    puts("-1");
    return 0;
  }
  int ans = dis[s1][t1] + dis[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int tmp1 = min(dis[s1][i] + dis[j][t1], dis[s1][j] + dis[i][t1]);
      int tmp2 = min(dis[s2][i] + dis[j][t2], dis[s2][j] + dis[i][t2]);
      if (tmp1 + dis[i][j] <= l1 && tmp2 + dis[i][j] <= l2)
        ans = min(ans, tmp1 + tmp2 + dis[i][j]);
    }
  printf("%d", m - ans);
  return 0;
}
