#include <bits/stdc++.h>
using namespace std;
vector<int> G[3007];
int d[3007][3007];
bool inq[3007];
int n;
void spfa(int s) {
  queue<int> q;
  for (int i = 1; i <= n; i++) d[s][i] = 10000000;
  memset(inq, 0, sizeof(inq));
  d[s][s] = 0;
  q.push(s);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    inq[x] = false;
    for (int i = 0; i < G[x].size(); i++) {
      int v = G[x][i];
      if (d[s][v] > d[s][x] + 1) {
        d[s][v] = d[s][x] + 1;
        if (!inq[v]) {
          inq[v] = true;
          q.push(v);
        }
      }
    }
  }
}
int main() {
  int m, a, b;
  scanf("%d%d", &n, &m);
  int ans = -1;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) spfa(i);
  int s1, t1, l1, s2, t2, l2;
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  if (d[s1][t1] <= l1 && d[s2][t2] <= l2) {
    ans = max(ans, m - d[s1][t1] - d[s2][t2]);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int d1 = d[i][j];
      int ds1 = d[s1][i], ds2 = d[s2][i];
      int dt1 = d[j][t1], dt2 = d[j][t2];
      if (d1 + ds1 + dt1 <= l1 && d1 + ds2 + dt2 <= l2) {
        ans = max(ans, m - d1 - ds1 - ds2 - dt1 - dt2);
      }
      ds1 = d[s1][j];
      ds2 = d[s2][i];
      dt1 = d[t1][i];
      dt2 = d[t2][j];
      if (ds1 + dt1 + d1 <= l1 && d1 + ds2 + dt2 <= l2) {
        ans = max(ans, m - d1 - ds1 - ds2 - dt1 - dt2);
      }
    }
  printf("%d\n", ans);
}
