#include <bits/stdc++.h>
using namespace std;
const int MAX_COUNT = 3001;
vector<int> graph[MAX_COUNT];
int d[MAX_COUNT][MAX_COUNT];
int main() {
  int vCount, eCount;
  scanf("%d%d", &vCount, &eCount);
  for (int i = 0; i < eCount; i++) {
    int from, to;
    scanf("%d%d", &from, &to);
    from--;
    to--;
    graph[from].push_back(to);
    graph[to].push_back(from);
  }
  for (int curV = 0; curV < vCount; curV++) {
    queue<int> q;
    q.push(curV);
    for (int i = 0; i < vCount; i++) d[curV][i] = -1;
    d[curV][curV] = 0;
    while (q.size()) {
      int v = q.front();
      q.pop();
      for (int i = 0; i < graph[v].size(); i++) {
        int to = graph[v][i];
        if (d[curV][to] == -1) {
          d[curV][to] = d[curV][v] + 1;
          q.push(to);
        }
      }
    }
  }
  int from1, to1, limit1;
  int from2, to2, limit2;
  scanf("%d%d%d", &from1, &to1, &limit1);
  scanf("%d%d%d", &from2, &to2, &limit2);
  from1--;
  from2--;
  to1--;
  to2--;
  int ans = d[from1][to1] + d[from2][to2];
  for (int start = 0; start < vCount; start++)
    for (int fin = 0; fin < vCount; fin++)
      if (d[from1][start] >= 0 && d[start][fin] >= 0 && d[to1][fin] >= 0 &&
          d[from2][fin] >= 0 && d[to2][fin] >= 0) {
        int d1 =
            min(d[from1][start] + d[to1][fin], d[to1][start] + d[from1][fin]) +
            d[start][fin];
        int d2 =
            min(d[from2][start] + d[to2][fin], d[to2][start] + d[from2][fin]) +
            d[start][fin];
        if (d1 <= limit1 && d2 <= limit2) {
          ans = min(ans, d1 + d2 - d[start][fin]);
        }
      }
  if (d[from1][to1] > limit1 || d[from2][to2] > limit2 || ans < 0)
    puts("-1");
  else
    printf("%d\n", eCount - ans);
  cin.get();
  cin.get();
  return 0;
}
