#include <bits/stdc++.h>
using namespace std;
struct pairhash {
 public:
  template <typename T, typename U>
  size_t operator()(const pair<T, U> &x) const {
    size_t seed = hash<T>()(x.first);
    return hash<U>()(x.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
};
const int inf = 1000000009;
const double eps = 1e-8;
vector<int> g[3010];
int d[3010][3010];
void bfs(int n) {
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) d[i][j] = inf;
    d[i][i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    bool used[n + 1];
    memset(used, false, sizeof(used));
    queue<int> que;
    queue<int> dis;
    que.push(i);
    dis.push(0);
    while (!que.empty()) {
      int idx = que.front();
      que.pop();
      int t = dis.front();
      dis.pop();
      if (!used[idx]) {
        used[idx] = true;
        d[i][idx] = t;
        for (int j = 0; j < g[idx].size(); j++) {
          int l = g[idx][j];
          if (!used[l]) {
            que.push(l);
            dis.push(t + 1);
          }
        }
      }
    }
  }
}
int solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int s[2], t[2], l[2];
  for (int i = 0; i < 2; i++) cin >> s[i] >> t[i] >> l[i];
  bfs(n);
  if (d[s[0]][t[0]] <= l[0] && d[s[1]][t[1]] <= l[1]) {
    int mini = d[s[0]][t[0]] + d[s[1]][t[1]];
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (d[s[0]][i] + d[i][j] + d[j][t[0]] <= l[0]) {
          if (d[s[1]][i] + d[i][j] + d[j][t[1]] <= l[1])
            mini = min(mini, d[s[0]][i] + d[s[1]][i] + d[i][j] + d[j][t[0]] +
                                 d[j][t[1]]);
          if (d[s[1]][j] + d[j][i] + d[i][t[1]] <= l[1])
            mini = min(mini, d[s[0]][i] + d[s[1]][j] + d[i][j] + d[j][t[0]] +
                                 d[i][t[1]]);
        }
      }
    }
    return m - mini;
  } else {
    return -1;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  cout << solve() << '\n';
}
