#include <bits/stdc++.h>
using namespace std;
vector<int> a[3001];
int d[3001][3001];
int n, e;
int z[2][3];
int main() {
  int i, j;
  int x, y;
  cin >> n >> e;
  for (i = 0; i < e; ++i) {
    cin >> x >> y;
    x--;
    y--;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  int t;
  for (i = 0; i < 2; ++i)
    for (j = 0; j < 3; ++j) {
      cin >> z[i][j];
      if (j != 2) z[i][j]--;
    }
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j) d[i][j] = 3001;
  for (i = 0; i < n; ++i) {
    d[i][i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      t = q.front();
      q.pop();
      int s = a[t].size();
      for (j = 0; j < s; ++j) {
        if (d[i][t] + 1 < d[i][a[t][j]]) {
          d[i][a[t][j]] = d[i][t] + 1;
          q.push(a[t][j]);
        }
      }
    }
  }
  int l, r;
  int mn = 3001 + 2;
  int k;
  for (k = 0; k < 2; ++k) {
    swap(z[0][0], z[0][1]);
    for (i = 0; i < n; ++i)
      for (j = 0; j < n; ++j) {
        l = d[z[0][0]][i] + d[i][j] + d[j][z[0][1]];
        r = d[z[1][0]][i] + d[i][j] + d[j][z[1][1]];
        if (l <= z[0][2] && r <= z[1][2]) {
          if (l + r - d[i][j] < mn) mn = l + r - d[i][j];
        }
      }
  }
  l = d[z[0][0]][z[0][1]];
  r = d[z[1][0]][z[1][1]];
  if (l <= z[0][2] && r <= z[1][2])
    if (l + r < mn) mn = l + r;
  cout << (mn < 3001 ? e - mn : -1) << endl;
  return 0;
}
