#include <bits/stdc++.h>
using namespace std;
int dist[3030][3030];
int main() {
  list<int> adj[3030];
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int n1, n2;
    scanf("%d%d", &n1, &n2);
    adj[n1].push_back(n2);
    adj[n2].push_back(n1);
  }
  for (int i = 1; i <= n; i++) {
    bool vis[3001] = {0};
    queue<pair<int, int> > bfs;
    bfs.push(make_pair(i, 0));
    vis[i] = 1;
    while (!bfs.empty()) {
      pair<int, int> temp = bfs.front();
      bfs.pop();
      dist[i][temp.first] = temp.second;
      list<int>::iterator it1 = adj[temp.first].begin();
      for (; it1 != adj[temp.first].end(); it1++) {
        if (vis[*it1]) continue;
        bfs.push(make_pair(*it1, temp.second + 1));
        vis[*it1] = 1;
      }
    }
  }
  int s1, s2, t1, t2, l1, l2;
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  if (dist[s1][t1] > l1 || dist[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int ansmin = 10000;
  ansmin = min(m + 1, dist[s1][t1] + dist[s2][t2]);
  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      int v1 = dist[s1][i] + dist[j][t1] + dist[i][j];
      int v2 = dist[s2][i] + dist[j][t2] + dist[i][j];
      if (v1 <= l1 && v2 <= l2) ansmin = min(ansmin, v1 + v2 - dist[i][j]);
      v1 = dist[s1][j] + dist[i][t1] + dist[i][j];
      v2 = dist[s2][i] + dist[j][t2] + dist[i][j];
      if (v1 <= l1 && v2 <= l2) ansmin = min(ansmin, v1 + v2 - dist[i][j]);
      v1 = dist[s1][j] + dist[i][t1] + dist[i][j];
      v2 = dist[s2][j] + dist[i][t2] + dist[i][j];
      if (v1 <= l1 && v2 <= l2) ansmin = min(ansmin, v1 + v2 - dist[i][j]);
      v1 = dist[s1][i] + dist[j][t1] + dist[i][j];
      v2 = dist[s2][j] + dist[i][t2] + dist[i][j];
      if (v1 <= l1 && v2 <= l2) ansmin = min(ansmin, v1 + v2 - dist[i][j]);
    }
  }
  if (ansmin > m)
    printf("-1\n");
  else
    cout << m - ansmin << endl;
  return 0;
}
