#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
vector<int> G[maxn];
int n, dis[maxn][maxn];
bool vis[maxn];
void bfs(int start) {
  for (int u = 1; u <= n; u++) dis[start][u] = 100000;
  queue<int> q;
  q.push(start);
  dis[start][start] = 0;
  memset(vis, false, sizeof(vis));
  vis[start] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = 0; v < G[u].size(); v++) {
      if (!vis[G[u][v]]) {
        vis[G[u][v]] = true;
        dis[start][G[u][v]] = dis[start][u] + 1;
        q.push(G[u][v]);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  int m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    bfs(i);
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    cout << -1 << endl;
    return 0;
  }
  int res = 1e9;
  for (int u = 1; u <= n; u++) {
    for (int v = 1; v <= n; v++) {
      if (dis[s1][u] + dis[v][t1] + dis[u][v] <= l1 &&
          dis[s2][u] + dis[v][t2] + dis[u][v] <= l2) {
        res = min(
            res, dis[s1][u] + dis[v][t1] + dis[s2][u] + dis[v][t2] + dis[u][v]);
      }
      swap(s2, t2);
      if (dis[s1][u] + dis[v][t1] + dis[u][v] <= l1 &&
          dis[s2][u] + dis[v][t2] + dis[u][v] <= l2) {
        res = min(
            res, dis[s1][u] + dis[v][t1] + dis[s2][u] + dis[v][t2] + dis[u][v]);
      }
    }
  }
  res = min(res, dis[s1][t1] + dis[s2][t2]);
  cout << m - res << endl;
  return 0;
}
