#include <bits/stdc++.h>
using namespace std;
struct node {
  int distance[3001];
  vector<int> adjacent;
  node() {
    for (int i = 0; i <= 3000; i++) distance[i] = -1;
  }
};
void relaxed_BFS(node* vertices, int source) {
  vertices[source].distance[source] = 0;
  queue<int> serial;
  serial.push(source);
  while (serial.empty() != true) {
    int u = serial.front();
    serial.pop();
    for (int i = 0; i < vertices[u].adjacent.size(); i++) {
      int v = vertices[u].adjacent[i];
      if (vertices[v].distance[source] == -1) {
        vertices[v].distance[source] = vertices[u].distance[source] + 1;
        serial.push(v);
      }
    }
  }
}
int main() {
  int n, edge;
  scanf("%d %d", &n, &edge);
  node vertices[n + 1];
  int tmx, tmy;
  for (int i = 1; i <= edge; i++) {
    scanf("%d %d", &tmx, &tmy);
    vertices[tmx].adjacent.push_back(tmy);
    vertices[tmy].adjacent.push_back(tmx);
  }
  for (int i = 1; i <= n; i++) {
    relaxed_BFS(vertices, i);
  }
  int start[2], target[2], time[2];
  for (int i = 0; i < 2; i++) {
    scanf("%d %d %d", &start[i], &target[i], &time[i]);
  }
  int minimum = edge + 1;
  int time_for_0, time_for_1;
  for (int trn = 1; trn <= 2; trn++) {
    swap(start[0], target[0]);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        time_for_0 = vertices[i].distance[start[0]] + vertices[j].distance[i] +
                     vertices[target[0]].distance[j];
        time_for_1 = vertices[i].distance[start[1]] + vertices[j].distance[i] +
                     vertices[target[1]].distance[j];
        if (time_for_0 <= time[0] && time_for_1 <= time[1]) {
          minimum =
              min(minimum, (time_for_0 - vertices[j].distance[i] + time_for_1));
        }
      }
    }
  }
  if (vertices[target[0]].distance[start[0]] <= time[0] &&
      vertices[target[1]].distance[start[1]] <= time[1]) {
    minimum = min(minimum, vertices[target[0]].distance[start[0]] +
                               vertices[target[1]].distance[start[1]]);
  }
  if (minimum <= edge) {
    printf("%d\n", edge - minimum);
  } else {
    printf("-1\n");
  }
}
