#include <bits/stdc++.h>
using namespace std;
int n, m, s1, s2, t1, t2, l1, l2;
vector<int> adj[3333];
int dist[3333][3333];
void bfs(int index) {
  queue<int> q;
  q.push(index);
  dist[index][index] = 0;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int to : adj[cur]) {
      if (dist[index][to] != -1) continue;
      dist[index][to] = dist[index][cur] + 1;
      q.push(to);
    }
  }
}
int main() {
  while (scanf("%d %d", &n, &m) == 2) {
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < m; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      adj[--a].push_back(--b);
      adj[b].push_back(a);
    }
    scanf("%d %d %d", &s1, &t1, &l1);
    --s1, --t1;
    scanf("%d %d %d", &s2, &t2, &l2);
    --s2, --t2;
    for (int i = 0; i < n; i++) bfs(i);
    if (dist[s1][t1] > l1 || dist[s2][t2] > l2) {
      puts("-1");
      continue;
    }
    int ans = dist[s1][t1] + dist[s2][t2];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        {
          int p1 = dist[s1][i] + dist[i][j] + dist[j][t1];
          int p2 = dist[s2][i] + dist[i][j] + dist[j][t2];
          if (p1 <= l1 && p2 <= l2) ans = min(ans, p1 + p2 - dist[i][j]);
        }
        {
          int p1 = dist[t1][i] + dist[i][j] + dist[j][s1];
          int p2 = dist[s2][i] + dist[i][j] + dist[j][t2];
          if (p1 <= l1 && p2 <= l2) ans = min(ans, p1 + p2 - dist[i][j]);
        }
      }
    ans = m - ans;
    printf("%d\n", ans);
  }
  return 0;
}
