#include <bits/stdc++.h>
using namespace std;
struct Tedge {
  int x, y;
};
int n, m, s1, t1, l1, s2, t2, l2, l;
int head[3007], link[3007 * 2], d[3007][3007];
bool check[3007];
Tedge e[3007 * 2];
queue<int> q;
void Bfs(int x) {
  int i, u, v;
  while (!q.empty()) q.pop();
  memset(check, true, sizeof(check));
  check[x] = false;
  int count_ = 0;
  q.push(x);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    i = head[u];
    while (i != 0) {
      v = e[i].y;
      if (check[v]) {
        d[x][v] = d[x][u] + 1;
        q.push(v);
        check[v] = false;
      }
      i = link[i];
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> e[i].x >> e[i].y;
    e[i + m].x = e[i].y;
    e[i + m].y = e[i].x;
  }
  for (int i = 1; i <= 2 * m; i++) {
    link[i] = head[e[i].x];
    head[e[i].x] = i;
  }
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  memset(d, 0, sizeof(d));
  for (int i = 1; i <= n; i++) Bfs(i);
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << -1;
    return 0;
  }
  int ans = m - d[s1][t1] - d[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2) {
        int temp = m - d[s1][i] - d[i][j] - d[j][t1] - d[s2][i] - d[j][t2];
        if (ans < temp) {
          ans = temp;
        }
      }
      if (d[s1][j] + d[i][j] + d[i][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2) {
        int temp = m - d[s1][j] - d[i][j] - d[i][t1] - d[s2][i] - d[j][t2];
        if (ans < temp) {
          ans = temp;
        }
      }
    }
  cout << ans;
}
