#include <bits/stdc++.h>
using namespace std;
int n, m;
int s0, t0, l0, s1, t1, l1;
int dist[3001][3001];
vector<int> adj[3001];
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  cin >> s0 >> t0 >> l0;
  cin >> s1 >> t1 >> l1;
  for (int v = 1; v <= n; v++) {
    bool vis[3001];
    for (int i = 1; i <= n; i++) vis[i] = 0;
    vector<int> q;
    q.push_back(v);
    vis[v] = 1;
    for (int i = 0; i < (int)q.size(); i++) {
      int u = q[i];
      for (int j = 0; j < (int)adj[u].size(); j++) {
        int w = adj[u][j];
        if (!vis[w]) {
          dist[v][w] = dist[v][u] + 1;
          vis[w] = 1;
          q.push_back(w);
        }
      }
    }
  }
  if (dist[s0][t0] > l0 || dist[s1][t1] > l1) {
    cout << -1;
  } else {
    int mp = dist[s0][t0] + dist[s1][t1];
    for (int v = 1; v <= n; v++) {
      for (int w = 1; w <= n; w++) {
        if (dist[s0][v] + dist[v][w] + dist[w][t0] <= l0 &&
            dist[s1][v] + dist[v][w] + dist[w][t1] <= l1)
          mp = min(mp, dist[s0][v] + dist[w][t0] + dist[s1][v] + dist[w][t1] +
                           dist[v][w]);
        if (dist[s0][w] + dist[w][v] + dist[v][t0] <= l0 &&
            dist[s1][v] + dist[v][w] + dist[w][t1] <= l1)
          mp = min(mp, dist[s0][w] + dist[v][t0] + dist[s1][v] + dist[w][t1] +
                           dist[v][w]);
      }
    }
    cout << m - mp;
  }
  return 0;
}
