#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
template <typename T>
string toString(const T &n) {
  ostringstream O;
  O << n;
  return O.str();
}
int n, m;
vector<int> edge[3000];
int s1, t1, l1;
int s2, t2, l2;
int d[3000][3000];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  scanf("%d %d %d", &s1, &t1, &l1);
  s1--;
  t1--;
  scanf("%d %d %d", &s2, &t2, &l2);
  s2--;
  t2--;
  memset(d, -1, sizeof(d));
  queue<int> q;
  for (int st = 0; st < n; st++) {
    d[st][st] = 0;
    q.push(st);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int i = 0; i < edge[cur].size(); i++) {
        int next_node = edge[cur][i];
        if (d[st][next_node] != -1) {
          continue;
        }
        q.push(next_node);
        d[st][next_node] = d[st][cur] + 1;
      }
    }
  }
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int sol = m - d[s1][t1] - d[s2][t2];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (d[s1][i] + d[i][j] + d[j][t1] > l1) continue;
      if (d[s2][i] + d[i][j] + d[j][t2] > l2) continue;
      sol = max(sol, m - d[s1][i] - d[i][j] - d[j][t1] - d[s2][i] - d[j][t2]);
      if (sol == 3) {
        sol = sol;
      }
    }
  }
  swap(s1, t1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (d[s1][i] + d[i][j] + d[j][t1] > l1) continue;
      if (d[s2][i] + d[i][j] + d[j][t2] > l2) continue;
      sol = max(sol, m - d[s1][i] - d[i][j] - d[j][t1] - d[s2][i] - d[j][t2]);
    }
  }
  printf("%d\n", sol);
  return 0;
}
