#include <bits/stdc++.h>
using namespace std;
using lli = long long;
using ld = long double;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
int n = 0, m = 0;
vector<vector<int>> data;
void BFS(vector<int>& dist, int s) {
  queue<int> q;
  q.push(s);
  dist[s] = 0;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : data[v]) {
      if (dist[u] > dist[v] + 1) {
        dist[u] = dist[v] + 1;
        q.push(u);
      }
    }
  }
}
int GetResult(vector<vector<int>>& dist, int s1, int t1, int l1, int s2, int t2,
              int l2) {
  int result = inf;
  if ((dist[s1][t1] <= l1) && (dist[s2][t2] <= l2))
    result = dist[s1][t1] + dist[s2][t2];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if ((dist[s1][i] + dist[i][j] + dist[j][t1] <= l1) &&
          (dist[s2][i] + dist[i][j] + dist[j][t2] <= l2)) {
        result = min(result, dist[s1][i] + dist[s2][i] + dist[i][j] +
                                 dist[j][t1] + dist[j][t2]);
      }
    }
  }
  return result;
}
inline void Solve() {
  cin >> n >> m;
  int s1 = 0, t1 = 0, l1 = 0, s2 = 0, t2 = 0, l2 = 0;
  data.resize(n);
  for (int i = 0; i < m; i++) {
    int a = 0, b = 0;
    cin >> a >> b;
    a--, b--;
    data[a].push_back(b);
    data[b].push_back(a);
  }
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  s1--, t1--;
  s2--, t2--;
  vector<vector<int>> dist(n, vector<int>(n, inf));
  for (int i = 0; i < n; i++) BFS(dist[i], i);
  int result = min(GetResult(dist, s1, t1, l1, s2, t2, l2),
                   GetResult(dist, t1, s1, l1, s2, t2, l2));
  if (result == inf)
    cout << -1;
  else
    cout << m - result;
}
signed main() {
  cout << fixed << setprecision(20);
  Solve();
  return 0;
}
