#include <bits/stdc++.h>
using namespace std;
vector<int> ad[3010];
vector<pair<int, int> > edges;
int n, m;
int s[2], t[2], l[2];
int d[3010][3010];
int vis[3010];
void bfs(int root) {
  fill(d[root], d[root] + n, 10e7);
  fill(vis, vis + n, 0);
  d[root][root] = 0;
  vis[root] = 1;
  queue<int> q;
  q.push(root);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = 0, sz = (int)ad[cur].size(); i < sz; i++) {
      if (!vis[ad[cur][i]]) {
        d[root][ad[cur][i]] = d[root][cur] + 1;
        vis[ad[cur][i]] = 1;
        q.push(ad[cur][i]);
      }
    }
  }
}
int main(void) {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    static int a, b;
    cin >> a >> b;
    a--;
    b--;
    ad[a].push_back(b);
    ad[b].push_back(a);
    edges.push_back(make_pair(a, b));
  }
  cin >> s[0] >> t[0] >> l[0];
  cin >> s[1] >> t[1] >> l[1];
  s[0]--;
  t[0]--;
  s[1]--;
  t[1]--;
  for (int i = 0; i < n; i++) bfs(i);
  int ans = m + 1;
  for (int iter = 0; iter < 2; iter++) {
    swap(s[0], t[0]);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int v[] = {d[s[0]][i] + d[i][j] + d[j][t[0]],
                   d[s[1]][i] + d[i][j] + d[j][t[1]]};
        if (v[0] <= l[0] && v[1] <= l[1]) {
          ans = min(ans, v[0] + v[1] - d[i][j]);
        }
      }
    }
  }
  if (d[s[0]][t[0]] <= l[0] && d[s[1]][t[1]] <= l[1]) {
    ans = min(ans, d[s[0]][t[0]] + d[s[1]][t[1]]);
  }
  if (ans > m) {
    ans = -1;
  } else {
    ans = m - ans;
  }
  printf("%d\n", ans);
  return 0;
}
