#include <bits/stdc++.h>   using namespace std;   long long gcd(long long a, long long b) { return (a ? gcd(b % a, a) : b); }   long long power(long long a, long long n) {     long long p = 1;     while (n > 0) {       if (n % 2) {         p = p * a;       }       n >>= 1;       a *= a;     }     return p;   }   const int maxN = 3000;   int dist[maxN + 10][maxN + 10], n, m, a, b, s[2], t[2], l[2], ans;   vector<int> e[maxN + 10];   void bfs(int u) {     memset(dist[u], -1, sizeof(dist[u]));     dist[u][u] = 0;     queue<int> q;     q.push(u);     while (!q.empty()) {       int x = q.front();       q.pop();       for (int i = 0; i < e[x].size(); i++) {         int y = e[x][i];         if (dist[u][y] == -1) {           dist[u][y] = dist[u][x] + 1;           q.push(y);         }       }     }   }   int main() {     ios_base::sync_with_stdio(false);     cin >> n >> m;     for (int i = 0; i < m; i++) {       cin >> a >> b;       a--;       b--;       e[a].push_back(b);       e[b].push_back(a);     }     for (int i = 0; i < 2; i++) {       cin >> s[i] >> t[i] >> l[i];       s[i]--;       t[i]--;     }     for (int i = 0; i < n; i++) {       bfs(i);     }     if (dist[s[0]][t[0]] > l[0] || dist[s[1]][t[1]] > l[1]) return cout << -1, 0;     ans = dist[s[0]][t[0]] + dist[s[1]][t[1]];     for (int i = 0; i < n; i++) {       for (int j = 0; j < n; j++) {         int d1 = dist[s[0]][i] + dist[i][j] + dist[j][t[0]];         int d2 = dist[s[1]][i] + dist[i][j] + dist[j][t[1]];         if (d1 <= l[0] && d2 <= l[1]) {           ans = min(ans, d1 + d2 - dist[i][j]);         }         d2 = dist[t[1]][i] + dist[i][j] + dist[j][s[1]];         if (d1 <= l[0] && d2 <= l[1]) {           ans = min(ans, d1 + d2 - dist[i][j]);         }         d1 = dist[t[0]][i] + dist[i][j] + dist[j][s[0]];         if (d1 <= l[0] && d2 <= l[1]) {           ans = min(ans, d1 + d2 - dist[i][j]);         }         d2 = dist[s[1]][i] + dist[i][j] + dist[j][t[1]];         if (d1 <= l[0] && d2 <= l[1]) {           ans = min(ans, d1 + d2 - dist[i][j]);         }       }     }     cout << m - ans;     return 0;   }   