#include <bits/stdc++.h>
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << ' ' << *it << " = " << a;
  err(++it, args...);
}
inline void op() { cout << '\n'; }
template <typename T, typename... Types>
inline void op(T var1, Types... var2) {
  cout << var1 << ' ';
  op(var2...);
}
inline void ip() {}
template <typename T, typename... Types>
inline void ip(T& var1, Types&... var2) {
  cin >> var1;
  ip(var2...);
}
template <typename T, typename U>
inline void min_self(T& x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void max_self(T& x, U y) {
  if (x < y) x = y;
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class T>
ostream& operator<<(ostream& out, vector<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ' ';
  return out << ")";
}
template <class T>
ostream& operator<<(ostream& out, set<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
template <class L, class R>
ostream& operator<<(ostream& out, map<L, R> vec) {
  out << "(";
  for (auto& v : vec) out << "[" << v.first << ", " << v.second << "]";
  return out << ")";
}
template <class A, class B>
istream& operator>>(istream& in, pair<A, B>& a) {
  return in >> a.first >> a.second;
}
template <class A>
istream& operator>>(istream& in, vector<A>& a) {
  for (A& i : a) in >> i;
  return in;
}
template <class Container>
void split(const std::string& str, Container& cont, char delim = ',') {
  stringstream ss(str);
  string token;
  while (std::getline(ss, token, delim)) {
    cont.push_back(token);
  }
}
long long px[4] = {-1, 0, 1, 0};
long long py[4] = {0, -1, 0, 1};
struct edge {
  long long u, v, wt;
  edge(long long a = 0, long long b = 0, long long c = 0) : u(a), v(b), wt(c) {}
  bool operator<(edge const& other) { return wt < other.wt; }
  friend ostream& operator<<(ostream& out, const edge& x) {
    return out << "(" << x.u << ", " << x.v << ", " << x.wt << ")";
  }
};
long long n, res = 0, m;
const long long maxn = 3005;
vector<long long> v[maxn];
long long s1, t1, l1, s2, t2, l2, dist[maxn][maxn];
bool vis[maxn];
void bfs(long long node) {
  for (long long i = 1; i <= n; i++) vis[i] = false;
  queue<long long> q;
  q.push(node);
  vis[node] = true;
  while (!q.empty()) {
    long long x = q.front();
    q.pop();
    for (long long i : v[x]) {
      if (!vis[i]) {
        vis[i] = true;
        dist[node][i] = dist[node][x] + 1;
        q.push(i);
      }
    }
  }
  return;
}
void abcd() {
  ip(n, m);
  long long x, y;
  for (long long i = 1; i <= m; i++) {
    ip(x, y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  ip(s1, t1, l1, s2, t2, l2);
  for (long long i = 1; i <= n; i++) bfs(i);
  if (dist[s1][t1] > l1 || dist[s2][t2] > l2) {
    op(-1);
    return;
  }
  res = max(0LL, m - dist[s1][t1] - dist[s2][t2]);
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      if (dist[s1][i] + dist[i][j] + dist[j][t1] <= l1 &&
          dist[s2][i] + dist[i][j] + dist[j][t2] <= l2)
        max_self(res, m - dist[s1][i] - dist[i][j] - dist[j][t1] - dist[s2][i] -
                          dist[j][t2]);
      if (dist[t1][i] + dist[i][j] + dist[j][s1] <= l1 &&
          dist[s2][i] + dist[i][j] + dist[j][t2] <= l2)
        max_self(res, m - dist[t1][i] - dist[i][j] - dist[j][s1] - dist[s2][i] -
                          dist[j][t2]);
    }
  }
  op(res);
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  while (t--) {
    abcd();
  }
  return 0;
}
