#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > AdjList;
int d[3005][3005];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  AdjList.assign(n, vector<int>());
  for (int i = (0); i < (m); ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--;
    v--;
    AdjList[u].push_back(v);
    AdjList[v].push_back(u);
  }
  for (int s = (0); s < (n); ++s) {
    queue<pair<int, int> > cola;
    vector<bool> visit(n);
    cola.push(make_pair(0, s));
    visit[s] = true;
    while (!cola.empty()) {
      int u = cola.front().second;
      int dist = cola.front().first;
      cola.pop();
      d[s][u] = dist;
      for (auto v : AdjList[u])
        if (!visit[v]) cola.push(make_pair(dist + 1, v)), visit[v] = true;
    }
  }
  int s1, t1, l1, s2, t2, l2;
  scanf("%d %d %d %d %d %d", &s1, &t1, &l1, &s2, &t2, &l2);
  s1--;
  t1--;
  s2--;
  t2--;
  int ans = -1;
  if (d[s1][t1] <= l1 and d[s2][t2] <= l2) ans = m - d[s1][t1] - d[s2][t2];
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) {
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 and
          d[s2][i] + d[i][j] + d[j][t2] <= l2)
        ans = max(ans, m - d[s1][i] - d[s2][i] - d[i][j] - d[j][t1] - d[j][t2]);
      if (d[t1][i] + d[i][j] + d[j][s1] <= l1 and
          d[s2][i] + d[i][j] + d[j][t2] <= l2)
        ans = max(ans, m - d[t1][i] - d[s2][i] - d[i][j] - d[j][s1] - d[j][t2]);
    }
  printf("%d\n", ans);
  return 0;
}
