#include <bits/stdc++.h>
using namespace std;
vector<int> nodes[3003];
int dist[3003][3003];
const int inf = 1000000000;
int n;
void bfs(int s) {
  for (int i = 1; i <= n; ++i) dist[s][i] = inf;
  dist[s][s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int j = 0; j < nodes[u].size(); j++) {
      int v = nodes[u][j];
      if (dist[s][v] > dist[s][u] + 1) {
        dist[s][v] = dist[s][u] + 1;
        q.push(v);
      }
    }
  }
}
int main() {
  int m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    nodes[u].push_back(v);
    nodes[v].push_back(u);
  }
  int s1, t1, s2, t2, l1, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  for (int i = 1; i <= n; ++i) {
    bfs(i);
  }
  if (dist[s1][t1] > l1 || dist[s2][t2] > l2) {
    return cout << "-1" << endl, 0;
  }
  int ans = dist[s1][t1] + dist[s2][t2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int b1 = min(dist[s1][i] + dist[j][t1], dist[s1][j] + dist[i][t1]);
      int b2 = min(dist[s2][i] + dist[j][t2], dist[s2][j] + dist[i][t2]);
      if (b1 + dist[i][j] <= l1 && b2 + dist[i][j] <= l2) {
        ans = min(ans, b1 + b2 + dist[i][j]);
      }
    }
  }
  cout << m - ans << endl;
}
