#include <bits/stdc++.h>
const double PI = 3.1415926535897932384626433;
const int KL = 3001;
const long long MOD = 1e9 + 7;
using namespace std;
int n, e, m, x, y, dis[KL], dp[KL][KL];
vector<int> adj[KL];
bool vis[KL];
void bfs(int src) {
  queue<int> q;
  q.push(src);
  vis[src] = 1;
  int len = 0;
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      int node = q.front();
      dis[node] = len;
      q.pop();
      for (auto v : adj[node])
        if (!vis[v]) vis[v] = true, q.push(v);
    }
    len++;
  }
}
int s1, s2, t1, t2, l1, l2;
int main() {
  scanf("%d", &n);
  scanf("%d", &e);
  for (int i = 0; i < e; i++) {
    scanf("%d", &x);
    scanf("%d", &y);
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  scanf("%d", &s1);
  scanf("%d", &t1);
  scanf("%d", &l1);
  scanf("%d", &s2);
  scanf("%d", &t2);
  scanf("%d", &l2);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) dis[j] = 0, vis[j] = false;
    bfs(i);
    for (int j = 1; j <= n; j++) dp[i][j] = dis[j];
  }
  if (dp[s1][t1] > l1 || dp[s2][t2] > l2) {
    printf("-1\n");
    return 0;
  }
  int mn = dp[s1][t1] + dp[s2][t2];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int sum1 = dp[s1][i] + dp[i][j] + dp[j][t1];
      int sum2 = dp[s2][i] + dp[i][j] + dp[j][t2];
      if (sum1 <= l1 && sum2 <= l2) mn = min(mn, sum1 + sum2 - dp[i][j]);
      sum1 = dp[s1][i] + dp[i][j] + dp[j][t1];
      sum2 = dp[t2][i] + dp[i][j] + dp[j][s2];
      if (sum1 <= l1 && sum2 <= l2) mn = min(mn, sum1 + sum2 - dp[i][j]);
    }
  }
  printf("%d\n", e - mn);
  return 0;
}
