#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
struct point {
  int st;
  int en;
  int ln;
};
int dist[3009][3009];
void bfs(int st, int index, int n) {
  int v;
  queue<int> q;
  q.push(st);
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (auto to : g[v]) {
      int cost = dist[st][v] + 1;
      if (cost < dist[st][to]) {
        dist[st][to] = cost;
        q.push(to);
      }
    }
  }
}
int getMin(int a, int b) { return a < b ? a : b; }
void findAns(int st1, int en1, int l1, int st2, int en2, int l2, int n, int m) {
  int temp1;
  int temp2;
  if (dist[st1][en1] > l1 || dist[st2][en2] > l2) {
    cout << "-1\n" << endl;
    return;
  }
  int ans = dist[st1][en1] + dist[st2][en2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      temp1 = getMin(dist[st1][i] + dist[i][j] + dist[j][en1],
                     dist[st1][j] + dist[i][j] + dist[i][en1]);
      temp2 = getMin(dist[st2][i] + dist[i][j] + dist[j][en2],
                     dist[st2][j] + dist[i][j] + dist[i][en2]);
      if (temp1 <= l1 && temp2 <= l2 && ans > (temp1 + temp2 - dist[i][j])) {
        ans = temp1 + temp2 - dist[i][j];
      }
    }
  if (ans == 2 * n + 1)
    cout << "-1\n" << endl;
  else
    cout << m - ans << endl;
}
void init(int n) {
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      dist[i][j] = 2 * n + 1;
    }
    dist[i][i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    bfs(i, i, n);
  }
}
int main() {
  int n, m, st, en;
  point pt[2];
  while (cin >> n >> m) {
    g.resize(n + 1);
    for (int i = 0; i < m; i++) {
      cin >> st >> en;
      g[st].push_back(en);
      g[en].push_back(st);
    }
    cin >> pt[0].st >> pt[0].en >> pt[0].ln;
    cin >> pt[1].st >> pt[1].en >> pt[1].ln;
    init(n);
    findAns(pt[0].st, pt[0].en, pt[0].ln, pt[1].st, pt[1].en, pt[1].ln, n, m);
  }
  return 0;
}
