思路：不在最短路径树上的边均可删去

WA #20

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

const int N = 3005, M = 3005;

int n, m;

struct edge {
    int to, nxt;
} e[M << 1];
int head[N], ecnt;
void add(int x, int y) {e[++ecnt] = {y, head[x]}, head[x] = ecnt;}

int dis[N];

int pre[N];

int s1, t1, s2, t2;

void spfa(int s) {
    queue<int> q;
    bitset<N> vis;
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                pre[v] = u;
                if (!vis[v])
                    q.push(v), vis[v] = 1;
            }
        }
    }
}

bool keep[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    cin >> s1 >> t1 >> s2 >> t2;
    spfa(1);
    if (dis[s1] > t1 || dis[s2] > t2) {
        cout << -1 << "\n";
        exit(0);
    }
    while (s1 != 1) keep[s1] = 1, s1 = pre[s1];
    while (s2 != 1) keep[s2] = 1, s2 = pre[s2];
    cout << m - accumulate(keep + 1, keep + 1 + n, 0) << "\n";
    return 0;
}