#include <bits/stdc++.h>
using namespace std;
const int maxn = 3000;
const int inf = 1e8;
struct edge {
  int start;
  int w;
};
int n, m;
int s1, t1, l1, s2, t2, l2;
int ans;
int vis[maxn + 5];
int dis[maxn + 5][maxn + 5];
vector<int> G[maxn + 5];
queue<edge> Q;
void bfs(int s) {
  memset(vis, 0, sizeof(vis));
  while (!Q.empty()) Q.pop();
  Q.push((edge){s, 0});
  vis[s] = 1;
  dis[s][s] = 0;
  while (!Q.empty()) {
    auto now = Q.front();
    Q.pop();
    for (int i = 0; i < G[now.start].size(); ++i) {
      auto x = G[now.start][i];
      if (!vis[x]) {
        Q.push((edge){x, now.w + 1});
        vis[x] = 1;
        dis[s][x] = now.w + 1;
      }
    }
  }
}
void check(int i, int j) {
  if (dis[i][s1] + dis[j][t1] + dis[i][j] <= l1 &&
      dis[i][s2] + dis[j][t2] + dis[i][j] <= l2) {
    ans = max(
        ans, m - dis[i][s1] - dis[j][t1] - dis[i][j] - dis[i][s2] - dis[j][t2]);
  }
  if (dis[i][s1] + dis[j][t1] + dis[i][j] <= l1 &&
      dis[j][s2] + dis[i][t2] + dis[i][j] <= l2) {
    ans = max(
        ans, m - dis[i][s1] - dis[j][t1] - dis[i][j] - dis[j][s2] - dis[i][t2]);
  }
  if (dis[j][s1] + dis[i][t1] + dis[i][j] <= l1 &&
      dis[i][s2] + dis[j][t2] + dis[i][j] <= l2) {
    ans = max(
        ans, m - dis[j][s1] - dis[i][t1] - dis[i][j] - dis[i][s2] - dis[j][t2]);
  }
  if (dis[j][s1] + dis[i][t1] + dis[i][j] <= l1 &&
      dis[j][s2] + dis[i][t2] + dis[i][j] <= l2) {
    ans = max(
        ans, m - dis[j][s1] - dis[i][t1] - dis[i][j] - dis[j][s2] - dis[i][t2]);
  }
}
int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) dis[i][j] = inf;
    bfs(i);
  }
  ans = -1;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) check(i, j);
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2)
    ans = max(ans, m - dis[s1][t1] - dis[s2][t2]);
  printf("%d\n", ans);
}
