#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 * 1000 + 10;
const int maxn5 = 5 * 1000 * 100 + 10;
const int maxn3 = 3000 + 10;
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1LL * 2 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 10;
int n, m, h[maxn3][maxn3];
vector<int> adj[maxn3];
queue<int> q;
void bfs(int root) {
  fill(h[root], h[root] + n + 10, -1);
  h[root][root] = 0;
  q.push(root);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto u : adj[v])
      if (h[root][u] == -1) {
        h[root][u] = h[root][v] + 1;
        q.push(u);
      }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  for (int i = 1; i <= n; i++) bfs(i);
  if (h[s1][t1] > l1 or h[s2][t2] > l2) return cout << -1 << endl, 0;
  long long ans = max(0, m - h[s1][t1] - h[s2][t2]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (h[s1][i] + h[i][j] + h[j][t1] <= l1 and
          h[s2][i] + h[i][j] + h[j][t2] <= l2)
        ans = max(ans, m - (0LL + h[s1][i] + h[s2][i] + h[i][j] + h[j][t1] +
                            h[j][t2]));
      if (h[s1][i] + h[i][j] + h[j][t1] <= l1 and
          h[s2][j] + h[i][j] + h[i][t2] <= l2)
        ans = max(ans, m - (0LL + h[s1][i] + h[s2][j] + h[i][j] + h[j][t1] +
                            h[i][t2]));
    }
  cout << ans << endl;
  return 0;
}
