#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 1000 + 13;
bool mark[MAXN][MAXN];
int dist[MAXN][MAXN];
queue<int> bfsq;
vector<int> adj[MAXN];
int main() {
  int n, m;
  cin >> n >> m;
  int a, b;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int s1, s2, t1, t2, l1, l2;
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  int u, v;
  for (int i = 1; i <= n; i++) {
    bfsq.push(i);
    mark[i][i] = true;
    dist[i][i] = 0;
    while (!bfsq.empty()) {
      u = bfsq.front();
      mark[u][i] = true;
      bfsq.pop();
      for (auto v : adj[u])
        if (!mark[v][i]) {
          dist[i][v] = dist[i][u] + 1;
          mark[v][i] = true;
          bfsq.push(v);
        }
    }
  }
  int ans = 0;
  bool poss = false;
  if ((dist[s1][t1] <= l1) and (dist[s2][t2] <= l2)) {
    ans = max(ans, m - dist[s1][t1] - dist[s2][t2]);
    poss = true;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (((dist[s1][i] + dist[i][j] + dist[j][t1]) <= l1) and
          ((dist[s2][i] + dist[i][j] + dist[j][t2]) <= l2)) {
        ans = max(ans, m - dist[s1][i] - dist[i][j] - dist[j][t1] -
                           dist[s2][i] - dist[j][t2]);
        poss = true;
      }
  swap(s1, t1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (((dist[s1][i] + dist[i][j] + dist[j][t1]) <= l1) and
          ((dist[s2][i] + dist[i][j] + dist[j][t2]) <= l2)) {
        ans = max(ans, m - dist[s1][i] - dist[i][j] - dist[j][t1] -
                           dist[s2][i] - dist[j][t2]);
        poss = true;
      }
  if (poss)
    cout << ans;
  else
    cout << -1;
  cout << endl;
  return 0;
}
