#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 1;
int n, m, d[N][N], k, s[2], t[2], l[2];
vector<int> a[N];
void Enter() {
  cin >> n >> m;
  int x, y;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  for (int i = 0; i <= 1; i++) cin >> s[i] >> t[i] >> l[i];
}
void BFS() {
  for (int i = 1; i <= n; i++) {
    queue<int> Q;
    Q.push(i);
    while (Q.size()) {
      int u = Q.front();
      Q.pop();
      for (int j = 0; j < a[u].size(); j++) {
        int v = a[u][j];
        if (d[i][v] == 0 && v != i) {
          d[i][v] = d[i][u] + 1;
          Q.push(v);
        }
      }
    }
  }
}
void Process() {
  int res;
  if (d[s[0]][t[0]] <= l[0] && d[s[1]][t[1]] <= l[1])
    res = d[s[0]][t[0]] + d[s[1]][t[1]];
  else
    res = m + 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int x = d[s[0]][i] + d[i][j] + d[j][t[0]];
      int y = d[s[1]][i] + d[i][j] + d[j][t[1]];
      int z = d[s[1]][j] + d[i][j] + d[i][t[1]];
      if (x <= l[0] && y <= l[1]) res = min(res, x + y - d[i][j]);
      if (x <= l[0] && z <= l[1]) res = min(res, x + z - d[i][j]);
    }
  if (res > m)
    cout << -1;
  else
    cout << m - res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  Enter();
  BFS();
  Process();
}
