#include <bits/stdc++.h>
using namespace std;
list<int> graph[3001];
bool visited[3001];
int shor[3001][3001];
void bfs(int v) {
  queue<int> q;
  q.push(v);
  shor[v][v] = 0;
  visited[v] = true;
  while (!q.empty()) {
    int fr = q.front();
    q.pop();
    for (list<int>::iterator it = graph[fr].begin(), end = graph[fr].end();
         it != end; it++) {
      int xx = *it;
      if (!visited[xx]) {
        visited[xx] = true;
        q.push(xx);
        shor[v][xx] = shor[v][fr] + 1;
      }
    }
  }
}
inline int dist(int s1, int i, int s2, int t1, int j, int t2, int l1, int l2) {
  if (shor[s1][i] + shor[i][j] + shor[j][t1] > l1 ||
      shor[s2][i] + shor[i][j] + shor[j][t2] > l2)
    return 1000000000;
  return shor[s1][i] + shor[s2][i] + shor[i][j] + shor[t1][j] + shor[t2][j];
}
int main() {
  stringstream ss;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int from, to;
    cin >> from >> to;
    from--;
    to--;
    graph[from].push_back(to);
    graph[to].push_back(from);
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  s1--;
  s2--;
  t1--;
  t2--;
  for (int i = 0; i < n; i++) {
    memset(visited, 0, sizeof(visited));
    bfs(i);
  }
  if (shor[s1][t1] > l1 || shor[s2][t2] > l2) {
    cout << "-1\n";
  } else {
    int mini = shor[s1][t1] + shor[s2][t2];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (j == i) continue;
        mini = min(mini, dist(s1, i, s2, t1, j, t2, l1, l2));
        mini = min(mini, dist(s1, i, t2, t1, j, s2, l1, l2));
      }
    }
    cout << m - mini << endl;
  }
}
