#include <bits/stdc++.h>
using namespace std;
long long n, m, d[(3222)][(3222)], x, y, l, x2, y2, l2;
vector<long long> e[(3222)];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < (3222); i++)
    for (int j = 0; j < (3222); j++) d[i][j] = ((long long)1e9);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    long long v, u;
    cin >> v >> u;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  cin >> x >> y >> l >> x2 >> y2 >> l2;
  for (int i = 1; i <= n; i++) {
    queue<long long> q;
    bool mark[(3222)] = {};
    mark[i] = 1;
    q.push(i);
    d[i][i] = 0;
    while (q.size()) {
      long long a = q.front();
      q.pop();
      for (int j = 0; j < e[a].size(); j++)
        if (!mark[e[a][j]])
          q.push(e[a][j]), d[i][e[a][j]] = d[i][a] + 1, mark[e[a][j]] = 1;
    }
  }
  long long ans = ((long long)1e9);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (d[x][i] + d[i][j] + d[j][y] <= l &&
          d[x2][i] + d[i][j] + d[j][y2] <= l2)
        ans = min(ans, d[x][i] + d[x2][i] + d[i][j] + d[j][y] + d[j][y2]);
      if (d[x][i] + d[i][j] + d[j][y] <= l &&
          d[y2][i] + d[i][j] + d[j][x2] <= l2)
        ans = min(ans, d[x][i] + d[y2][i] + d[i][j] + d[j][y] + d[j][x2]);
    }
  if (ans == ((long long)1e9) && (d[x][y] > l || d[x2][y2] > l2))
    return cout << -1, 0;
  cout << m - ((ans == ((long long)1e9)) ? d[x][y] + d[x2][y2]
                                         : min(ans, d[x][y] + d[x2][y2]));
  return 0;
}
