#include <bits/stdc++.h>
using namespace std;
vector<int> g[3010];
int n, m;
bool vis[3010];
int dis[3010][3010];
void init() {
  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++) {
    queue<int> q;
    memset(vis, false, sizeof(vis));
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      int siz = g[u].size();
      for (int j = 0; j < siz; j++)
        if (!vis[g[u][j]]) {
          dis[i][g[u][j]] = dis[i][u] + 1;
          vis[g[u][j]] = true;
          q.push(g[u][j]);
        }
    }
  }
}
int s1, t1, l1, s2, t2, l2;
int main() {
  init();
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  if (!(dis[s1][t1] <= l1 && dis[s2][t2] <= l2)) {
    cout << "-1\n";
    return 0;
  }
  int tmp = dis[s1][t1] + dis[s2][t2];
  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[s1][i] + dis[i][j] + dis[j][t2] <= l2)
        if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
            dis[t2][i] + dis[i][j] + dis[i][s2] <= l2)
          tmp = min(tmp, dis[s1][i] + dis[i][j] + dis[j][t1] + dis[t2][i] +
                             dis[i][s2]);
      if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
        tmp = min(
            tmp, dis[t1][i] + dis[i][j] + dis[j][s1] + dis[s2][i] + dis[j][t2]);
      if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1 &&
          dis[t2][i] + dis[i][j] + dis[j][s2] <= l2)
        tmp = min(
            tmp, dis[t1][i] + dis[i][j] + dis[j][s1] + dis[t2][i] + dis[j][s2]);
    }
  cout << m - tmp;
  return 0;
}
