#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
int n, m;
vector<int> ans;
vector<int> v[N];
int d[N][N];
vector<int> check;
bool mark[N];
int s1, s2, e1, e2, l1, l2;
void bfs(int s) {
  check.clear();
  int p = 0;
  check.push_back(s);
  for (int i = 0; i < N; ++i) mark[i] = false;
  int now, kid;
  d[s][s] = 0;
  mark[s] = true;
  while (p != check.size()) {
    now = check[p];
    for (int i = 0; i < v[now].size(); ++i) {
      kid = v[now][i];
      if (mark[kid]) continue;
      d[s][kid] = d[s][now] + 1;
      mark[kid] = true;
      check.push_back(kid);
    }
    p++;
  }
}
int main() {
  cin >> n >> m;
  int help1, help2;
  for (int i = 0; i < m; ++i) {
    cin >> help1 >> help2;
    v[help1].push_back(help2);
    v[help2].push_back(help1);
  }
  cin >> s1 >> e1 >> l1 >> s2 >> e2 >> l2;
  for (int i = 1; i < n + 1; ++i) bfs(i);
  if ((d[s1][e1] > l1) || (d[s2][e2] > l2)) return cout << -1, 0;
  ans.push_back(d[s1][e1] + d[s2][e2]);
  for (int i = 1; i < n + 1; ++i)
    for (int j = 1; j < n + 1; ++j) {
      if ((d[s1][i] + d[i][j] + d[j][e1] <= l1) &&
          (d[s2][i] + d[i][j] + d[j][e2] <= l2)) {
        ans.push_back(d[s1][i] + d[s2][i] + d[i][j] + d[j][e1] + d[j][e2]);
      }
      swap(s1, e1);
      if ((d[s1][i] + d[i][j] + d[j][e1] <= l1) &&
          (d[s2][i] + d[i][j] + d[j][e2] <= l2)) {
        ans.push_back(d[s1][i] + d[s2][i] + d[i][j] + d[j][e1] + d[j][e2]);
      }
    }
  int mii = 1e8;
  for (int i = 0; i < ans.size(); ++i) mii = min(mii, ans[i]);
  cout << m - mii;
}
