#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
struct Edge {
  int u, v, nxt;
} edge[maxn << 2];
int head[maxn], cnt = -1;
inline void add_edge(int u, int v) {
  edge[++cnt] = {u, v, head[u]};
  head[u] = cnt;
  edge[++cnt] = {v, u, head[v]};
  head[v] = cnt;
}
long long dis[maxn][maxn];
inline void bfs(int s1) {
  queue<int> q;
  q.push(s1);
  dis[s1][s1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      Edge &e = edge[i];
      if (dis[s1][e.v] > dis[s1][u] + 1) {
        dis[s1][e.v] = dis[s1][u] + 1;
        q.push(e.v);
      }
    }
  }
}
int main() {
  memset(head, -1, sizeof(head));
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      dis[i][j] = 1e9;
    }
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    add_edge(u, v);
  }
  for (int i = 1; i <= n; ++i) {
    bfs(i);
  }
  long long s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  long long ans = -1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 &&
          dis[s2][i] + dis[i][j] + dis[j][t2] <= l2) {
        ans = max(ans, m - 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 = max(ans, m - dis[s1][i] - dis[j][t1] - dis[t2][i] - dis[i][j] -
                           dis[j][s2]);
      }
    }
  }
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2) {
    ans = max(ans, m - dis[s1][t1] - dis[s2][t2]);
  }
  cout << ans << endl;
  return 0;
}
