#include <bits/stdc++.h>
using namespace std;
const int mxn = 3005, inf = 1e9 + 5;
int n, m, x, y, s1, t1, l1, s2, t2, l2, dis[mxn][mxn], mark[mxn], ans;
vector<int> adj[mxn];
void bfs(int v) {
  for (int i = 1; i <= n; i++) mark[i] = 0;
  queue<int> q;
  q.push(v);
  mark[v] = 1;
  dis[v][v] = 0;
  while (q.size()) {
    int v1 = q.front();
    q.pop();
    for (auto u : adj[v1]) {
      if (!mark[u]) {
        q.push(u);
        dis[v][u] = dis[v][v1] + 1;
        mark[u] = 1;
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  for (int i = 1; i <= n; i++) bfs(i);
  ans = inf;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2) {
        ans = min(
            ans, dis[i][s1] + dis[i][s2] + dis[j][t1] + dis[j][t2] + dis[i][j]);
      }
      if (dis[s1][j] + dis[i][j] + dis[i][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2) {
        ans = min(
            ans, dis[j][s1] + dis[i][s2] + dis[i][t1] + dis[j][t2] + dis[i][j]);
      }
    }
  }
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2)
    ans = min(ans, dis[s1][t1] + dis[s2][t2]);
  cout << (ans == inf ? -1 : m - ans);
  return 0;
}
