95pts Code:

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> pii;

const int maxn = 3005;

struct node {
	vector<int> e;
	int dis = INT_MAX, pre;
} v[maxn];

#define Add_edge(x,y) v[x].e.emplace_back(y),v[y].e.emplace_back(x)

bool cnt[maxn][maxn];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	v[start].dis = 0;
	v[start].pre = -1;
	while (q.size()) {
		int front = q.front();
		q.pop();
		for (auto& x : v[front].e) {
			if (v[front].dis + 1 <= v[x].dis) {
				v[x].dis = v[front].dis + 1;
				v[x].pre = front;
				q.push(x);
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;
		Add_edge(x, y);
	}
	bfs(1);
	int s1, s2, t1, t2;
	cin >> s1 >> t1 >> s2 >> t2;
	if (v[s1].dis == INT_MAX || v[s2].dis == INT_MAX) {
		cout << -1;
		return 0;
	}
	if (v[s1].dis > t1 || v[s2].dis > t2) cout << -1;
	else if (s1 == s2) {
		cout << m - v[s1].dis;
	} else {
		int ans = 0;
		for (int i = s1; ~i; i = v[i].pre) {
			if (~v[i].pre) {
				ans += !cnt[v[i].pre][i];
				cnt[v[i].pre][i] = true;
			}
		}
		for (int i = s2; ~i; i = v[i].pre) {
			if (~v[i].pre) {
				ans += !cnt[v[i].pre][i];
				cnt[v[i].pre][i] = true;
			}
		}
		cout << m - ans;
	}
	return 0;
}