#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn = 3010;
vector<int> g[maxn];
int vis[maxn], dis[maxn][maxn];
void bfs(int s) {
  memset(vis, 0, sizeof(vis));
  queue<int> que;
  que.push(s);
  vis[s] = 1;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i];
      if (vis[v]) continue;
      vis[v] = 1;
      dis[s][v] = dis[s][u] + 1;
      que.push(v);
    }
  }
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 0; i <= n; i++) g[i].clear();
    for (int i = 0; i < m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
    }
    int s1, t1, d1, s2, t2, d2;
    scanf("%d%d%d%d%d%d", &s1, &t1, &d1, &s2, &t2, &d2);
    for (int i = 1; i <= n; i++) bfs(i);
    if (dis[s1][t1] > d1 || dis[s2][t2] > d2) {
      puts("-1");
      continue;
    }
    int ans = dis[s1][t1] + dis[s2][t2];
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (dis[s1][i] + dis[i][j] + dis[j][t1] <= d1 &&
            dis[s2][i] + dis[i][j] + dis[j][t2] <= d2)
          ans = min(ans, dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] +
                             dis[j][t2]);
        if (dis[s1][i] + dis[i][j] + dis[j][t1] <= d1 &&
            dis[t2][i] + dis[i][j] + dis[j][s2] <= d2)
          ans = min(ans, dis[s1][i] + dis[i][j] + dis[j][t1] + dis[t2][i] +
                             dis[j][s2]);
        if (dis[t1][i] + dis[i][j] + dis[j][s1] <= d1 &&
            dis[s2][i] + dis[i][j] + dis[j][t2] <= d2)
          ans = min(ans, dis[t1][i] + dis[i][j] + dis[j][s1] + dis[s2][i] +
                             dis[j][t2]);
        if (dis[t1][i] + dis[i][j] + dis[j][s1] <= d1 &&
            dis[t2][i] + dis[i][j] + dis[j][s2] <= d2)
          ans = min(ans, dis[t1][i] + dis[j][s1] + dis[t2][i] + dis[i][j] +
                             dis[j][s2]);
      }
    cout << m - ans << endl;
  }
  return 0;
}
