#include <bits/stdc++.h>
const double EPS = 1e-24;
const long long int MOD = 1000000007ll;
const double PI = 3.14159265359;
int INF = 2147483645;
template <class T>
T Max2(T a, T b) {
  return a < b ? b : a;
}
template <class T>
T Min2(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T Max3(T a, T b, T c) {
  return Max2(Max2(a, b), c);
}
template <class T>
T Min3(T a, T b, T c) {
  return Min2(Min2(a, b), c);
}
template <class T>
T Max4(T a, T b, T c, T d) {
  return Max2(Max2(a, b), Max2(c, d));
}
template <class T>
T Min4(T a, T b, T c, T d) {
  return Min2(Min2(a, b), Max2(c, d));
}
template <class T>
void Swap(T& a, T& b) {
  T temp;
  temp = a;
  a = b;
  b = temp;
}
using namespace std;
int N, M;
vector<int> G[3001];
int d[3001][3001];
int s1, s2, t1, t2, l1, l2;
bool vis[3001];
void bfs(int c) {
  for (int i = 1; i <= N; i++) vis[i] = false;
  d[c][c] = 0;
  queue<int> Q;
  Q.push(c);
  vis[c] = true;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (!vis[v]) {
        vis[v] = true;
        Q.push(v);
        d[c][v] = d[c][u] + 1;
      }
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> N >> M;
  for (int i = 1; i <= M; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  queue<int> Q;
  for (int i = 1; i <= N; i++) bfs(i);
  if (d[s1][t1] > l1 || d[s2][t2] > l2) {
    cout << "-1";
    return 0;
  }
  int ans = d[s1][t1] + d[s2][t2];
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2)
        ans = Min2(ans, d[s1][i] + d[s2][i] + d[i][j] + d[j][t1] + d[j][t2]);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      if (d[s1][i] + d[i][j] + d[j][t1] <= l1 &&
          d[s2][j] + d[i][j] + d[i][t2] <= l2)
        ans = Min2(ans, d[s1][i] + d[s2][j] + d[i][j] + d[j][t1] + d[i][t2]);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      if (d[s1][j] + d[i][j] + d[i][t1] <= l1 &&
          d[s2][i] + d[i][j] + d[j][t2] <= l2)
        ans = Min2(ans, d[s1][j] + d[s2][i] + d[i][j] + d[i][t1] + d[j][t2]);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      if (d[s1][j] + d[i][j] + d[i][t1] <= l1 &&
          d[s2][j] + d[i][j] + d[i][t2] <= l2)
        ans = Min2(ans, d[s1][j] + d[s2][j] + d[i][j] + d[i][t1] + d[i][t2]);
  cout << M - ans;
  return 0;
}
