#include <bits/stdc++.h>
using namespace std;
const int INF = 0xfffffff;
const int SIZE = 3005;
int N, M, D[SIZE][SIZE];
int s_1, t_1, l_1, s_2, t_2, l_2;
bool S[SIZE];
struct Q_Node {
  int d, vec;
  bool operator<(const Q_Node& r) const { return d > r.d; };
};
vector<int> G[SIZE];
void dijkstra(int);
int main(void) {
  int from, to;
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++) {
    scanf("%d%d", &from, &to);
    G[from].push_back(to);
    G[to].push_back(from);
  }
  for (int i = 1; i <= N; i++) dijkstra(i);
  scanf("%d%d%d", &s_1, &t_1, &l_1);
  scanf("%d%d%d", &s_2, &t_2, &l_2);
  if (D[s_1][t_1] > l_1 || D[s_2][t_2] > l_2) {
    puts("-1");
    return 0;
  }
  int min = D[s_1][t_1] + D[s_2][t_2];
  int ans = 0;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      if (min > D[s_1][i] + D[s_2][i] + D[i][j] + D[j][t_1] + D[j][t_2])
        if (D[s_1][i] + D[i][j] + D[j][t_1] <= l_1 &&
            D[s_2][i] + D[i][j] + D[j][t_2] <= l_2)
          min = D[s_1][i] + D[s_2][i] + D[i][j] + D[j][t_1] + D[j][t_2];
      if (min > D[t_1][i] + D[s_2][i] + D[i][j] + D[j][s_1] + D[j][t_2])
        if (D[t_1][i] + D[i][j] + D[j][s_1] <= l_1 &&
            D[s_2][i] + D[i][j] + D[j][t_2] <= l_2)
          min = D[t_1][i] + D[s_2][i] + D[i][j] + D[j][s_1] + D[j][t_2];
    }
  printf("%d\n", M - min);
  return 0;
}
void dijkstra(int s) {
  priority_queue<Q_Node> que;
  Q_Node temp;
  for (int i = 0; i <= N; i++) {
    D[s][i] = INF;
    S[i] = false;
  }
  D[s][s] = 0;
  temp.d = 0;
  temp.vec = s;
  que.push(temp);
  while (!que.empty()) {
    int cur = que.top().vec;
    que.pop();
    S[cur] = true;
    for (int i = 0; i < G[cur].size(); i++)
      if (!S[G[cur][i]] && D[s][G[cur][i]] > D[s][cur] + 1) {
        D[s][G[cur][i]] = D[s][cur] + 1;
        temp.vec = G[cur][i];
        temp.d = D[s][G[cur][i]];
        que.push(temp);
      }
  }
}
