#include <bits/stdc++.h>
using namespace std;
struct DD {
  int v;
  int l;
};
vector<DD> G[3005];
int n, m;
int t1, t2;
int f1, e1, limit1;
int f2, e2, limit2;
int flag = 1;
int ans;
bool vis[3005];
int dist[3005][3005];
int bfs(int f) {
  memset(vis, 0, sizeof(vis));
  DD t, x;
  int t1, t2, size;
  t.v = f;
  t.l = 0;
  queue<DD> q;
  q.push(t);
  vis[t.v] = 1;
  while (!q.empty()) {
    vis[t.v] = 1;
    t = q.front();
    q.pop();
    size = G[t.v].size();
    for (int i = 0; i < size; i++) {
      x = G[t.v][i];
      if (!vis[x.v]) {
        x.l = t.l + 1;
        dist[f][x.v] = min(x.l, dist[f][x.v]);
        q.push(x);
      }
    }
  }
  return 1;
}
int main() {
  DD tt;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 0; i <= n; i++) memset(dist[i], 0x3f, sizeof(dist[i]));
    for (int i = 0; i <= n; i++) dist[i][i] = 0;
    for (int i = 0; i <= n; i++) G[i].clear();
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &t1, &t2);
      tt.v = t2;
      G[t1].push_back(tt);
      tt.v = t1;
      G[t2].push_back(tt);
    }
    scanf("%d%d%d", &f1, &e1, &limit1);
    scanf("%d%d%d", &f2, &e2, &limit2);
    for (int i = 1; i <= n; i++) bfs(i);
    if (dist[f1][e1] > limit1 || dist[f2][e2] > limit2)
      printf("-1\n");
    else {
      ans = dist[f1][e1] + dist[f2][e2];
      for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
          if (dist[f1][i] + dist[i][j] + dist[j][e1] <= limit1 &&
              dist[f2][i] + dist[i][j] + dist[j][e2] <= limit2)
            ans = min(ans, dist[f1][i] + dist[i][j] + dist[j][e1] +
                               dist[f2][i] + dist[j][e2]);
          if (dist[f1][i] + dist[i][j] + dist[j][e1] <= limit1 &&
              dist[f2][j] + dist[j][i] + dist[i][e2] <= limit2)
            ans = min(ans, dist[f1][i] + dist[i][j] + dist[j][e1] +
                               dist[f2][j] + dist[i][e2]);
          if (dist[f1][j] + dist[j][i] + dist[i][e1] <= limit1 &&
              dist[f2][i] + dist[i][j] + dist[j][e2] <= limit2)
            ans = min(ans, dist[f1][j] + dist[j][i] + dist[i][e1] +
                               dist[f2][i] + dist[j][e2]);
          if (dist[f1][j] + dist[j][i] + dist[i][e1] <= limit1 &&
              dist[f2][j] + dist[j][i] + dist[i][e2] <= limit2)
            ans = min(ans, dist[f1][j] + dist[j][i] + dist[i][e1] +
                               dist[f2][j] + dist[i][e2]);
        }
      }
      printf("%d\n", m - ans);
    }
  }
  return 0;
}
