#include <bits/stdc++.h>
using namespace std;
int jsj = 0x3f3f3f3f;
int n, m, s1, t1, s2, t2, l1, l2;
struct p {
  int dian, juli;
  bool operator<(const p& a) const { return juli > a.juli; }
};
int biaoji[3005][3001], daon[3001][3001], qid[3001];
vector<int> tu[3001];
int main() {
  cin >> n >> m;
  int q, w;
  for (int a = 1; a <= m; a++) {
    cin >> q >> w;
    tu[q].push_back(w);
    tu[w].push_back(q);
  }
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  for (int a = 1; a <= n; a++) qid[a] = a;
  priority_queue<p> qq[3005];
  memset(daon, 0x3f, sizeof(daon));
  for (int a = 1; a <= n; a++) {
    daon[a][qid[a]] = 0;
    qq[a].push({qid[a], 0});
    while (!qq[a].empty()) {
      p we = qq[a].top();
      qq[a].pop();
      if (biaoji[a][we.dian]) continue;
      biaoji[a][we.dian] = 1;
      for (int b = 0; b < tu[we.dian].size(); b++) {
        if (biaoji[a][tu[we.dian][b]]) continue;
        if (daon[a][tu[we.dian][b]] > daon[a][we.dian] + 1) {
          daon[a][tu[we.dian][b]] = daon[a][we.dian] + 1;
          qq[a].push({tu[we.dian][b], daon[a][tu[we.dian][b]]});
        }
      }
    }
  }
  int jccc = 0;
  int zhijie = daon[s1][t1] + daon[s2][t2];
  if (daon[s1][t1] > l1 || daon[s2][t2] > l2) jccc = 1;
  int jianjie = 0x3f3f3f3f;
  int jccc2 = 1;
  for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
      if (daon[a][b] == jsj || daon[a][s1] == jsj || daon[b][t1] == jsj ||
          daon[a][s2] == jsj || daon[b][t2] == jsj)
        continue;
      int tiaojian = daon[a][b] + daon[a][s1] + daon[b][t1],
          tiaojian2 = daon[a][b] + daon[b][s1] + daon[a][t1];
      int tiaojian3 = daon[a][b] + daon[a][s2] + daon[b][t2],
          tiaojian4 = daon[a][b] + daon[b][s2] + daon[a][t2];
      if (tiaojian <= l1 && tiaojian3 <= l2) {
        jccc2 = 0;
        jianjie = min(jianjie, tiaojian + tiaojian3 - daon[a][b]);
      }
      if (tiaojian2 <= l1 && tiaojian4 <= l2) {
        jccc2 = 0;
        jianjie = min(jianjie, tiaojian2 + tiaojian4 - daon[a][b]);
      }
      if (tiaojian <= l1 && tiaojian4 <= l2) {
        jccc2 = 0;
        jianjie = min(jianjie, tiaojian + tiaojian4 - daon[a][b]);
      }
      if (tiaojian2 <= l1 && tiaojian3 <= l2) {
        jccc2 = 0;
        jianjie = min(jianjie, tiaojian2 + tiaojian3 - daon[a][b]);
      }
    }
  }
  if (jccc && jccc2)
    cout << -1;
  else if (jccc == 0 && jccc2 == 1)
    cout << m - zhijie;
  else if (jccc2 == 0 && jccc == 1)
    cout << m - jianjie;
  else
    cout << m - min(zhijie, jianjie);
  return 0;
}
