#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<int> > G;
vector<vector<int> > D;
vector<int> done;
vector<int>::iterator it;
void bfs(int start) {
  D[start][start] = 0;
  queue<int> Q;
  vector<int> used(N, false);
  Q.push(start);
  used[start] = true;
  while (!Q.empty()) {
    int current = Q.front();
    Q.pop();
    int current_length = D[start][current];
    for (it = G[current].begin(); it != G[current].end(); it++) {
      if (!used[*it]) {
        D[start][*it] = current_length + 1;
        used[*it] = true;
        Q.push(*it);
      }
    }
  }
}
int main() {
  int a, b, i, j;
  int s1, s2, t1, t2, l1, l2;
  while (cin >> N >> M) {
    G.resize(N);
    D.resize(N);
    for (i = 0; i < N; i++) {
      G[i].clear();
      D[i].clear();
      D[i].resize(N, -12345678);
    }
    for (i = 0; i < M; i++) {
      cin >> a >> b;
      G[a - 1].push_back(b - 1);
      G[b - 1].push_back(a - 1);
    }
    for (i = 0; i < N; i++) {
      bfs(i);
    }
    cin >> s1 >> t1 >> l1;
    cin >> s2 >> t2 >> l2;
    if (D[s1 - 1][t1 - 1] > l1 || D[s2 - 1][t2 - 1] > l2) {
      printf("-1\n");
      continue;
    }
    int sum = M - D[s1 - 1][t1 - 1] - D[s2 - 1][t2 - 1];
    for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        int sum1 = D[s1 - 1][i] + D[i][j] + D[j][t1 - 1];
        int sum2 = D[s2 - 1][i] + D[i][j] + D[j][t2 - 1];
        if (sum1 <= l1 && sum2 <= l2) {
          int temp = M - sum1 - sum2 + D[i][j];
          if (temp > sum) sum = temp;
        }
        sum1 = D[s1 - 1][i] + D[i][j] + D[j][t1 - 1];
        sum2 = D[t2 - 1][i] + D[i][j] + D[j][s2 - 1];
        if (sum1 <= l1 && sum2 <= l2) {
          int temp = M - sum1 - sum2 + D[i][j];
          if (temp > sum) sum = temp;
        }
      }
    }
    cout << sum << "\n";
  }
  return 0;
}
