#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
const int Maxn = 3005;
using namespace std;
int n, m;
int s1, t1, l1;
int s2, t2, l2;
vector<int> vec[Maxn];
int dis[Maxn][Maxn];
bool vis[Maxn];
void spfa(int s) {
  queue<int> q;
  memset(vis, 0, sizeof(vis));
  q.push(s);
  dis[s][s] = 0;
  vis[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = 0; i < vec[u].size(); i++) {
      int v = vec[u][i];
      if (dis[s][v] > dis[s][u] + 1) {
        dis[s][v] = dis[s][u] + 1;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
}
int main() {
  int u, v;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  scanf("%d%d%d", &s1, &t1, &l1);
  scanf("%d%d%d", &s2, &t2, &l2);
  memset(dis, INF, sizeof(dis));
  for (int i = 1; i <= n; i++) spfa(i);
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    printf("-1");
    return 0;
  }
  int ans = dis[s1][t1] + dis[s2][t2];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)
        ans = min(
            ans, dis[s1][i] + dis[s2][i] + dis[i][j] + dis[j][t1] + dis[j][t2]);
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
          dis[t2][i] + dis[i][j] + dis[j][s2] <= l2)
        ans = min(
            ans, dis[s1][i] + dis[t2][i] + dis[i][j] + dis[j][t1] + dis[j][s2]);
    }
  printf("%d\n", m - ans);
  return 0;
}
