记录编号	578115	评测结果	AAAAAAAAAA
题目名称	[CSP JX2019PJ]道路拆除(民间数据)	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2023-02-01 16:23:16	内存使用	0.00 MiB

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N = 35001;
int dis1[35001], dis2[35001], dis3[35001];
vector<int> b[N];
pair<int,int> val[N * 4];
int n, m,a1,a2;
int S1, T1, S2, T2;
int ls(int x)
{
	return x << 1;
}
int rs(int x)
{
	return x << 1 | 1;
}
void pushup(int x)
{
	val[x] = min(val[ls(x)], val[rs(x)]);
}
void build(int x, int l, int r)
{
	val[x] = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
	if (l == r)
	{
		val[x] = make_pair(0x3f3f3f3f, l);
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	pushup(x);
}
pair<int, int> Check(int x, int l, int r,int nl,int nr)
{
	if (nl <= l && nr >= r)
	{
		return val[x];
	}
	int mid = (l + r) >> 1;
	pair<int, int> S = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
	if (nl <= mid)
	{
		S = min(S, Check(ls(x), l, mid, nl, nr));
	}
	if (nr > mid)
	{
		S = min(S, Check(rs(x), mid + 1, r, nl, nr));
	}
	return S;
}
void Update(int x, int l, int r, int Pos, pair<int, int> data)
{
	if (l == r)
	{
		val[x] = data;
		return;
	}
	int mid = (l + r) >> 1;
	if (Pos <= mid)
		Update(ls(x), l, mid, Pos, data);
	else
		Update(rs(x), mid + 1, r, Pos, data);
	pushup(x);
}
void DIJ(int S, int dis[])
{
	build(1, 1, n);	
	dis[S] = 0;
	Update(1, 1, n, S, make_pair(0, S));
	while (1)
	{
		pair<int, int > NOW = Check(1, 1, n, 1, n);
		if (NOW.first == 0x3f3f3f3f)
		{
			return;
		}
		int x = NOW.second;
		Update(1, 1, n, x, make_pair(0x3f3f3f3f, x));
	
		for (int i = 0; i < b[x].size(); i++)
		{
			int y = b[x][i];
			if (dis[y] > dis[x] + 1)
			{
				dis[y] = dis[x] + 1;
				Update(1, 1, n, y, make_pair(dis[y], y));
			}
		}
	}
}
int main()
{
	freopen("cspjx2019pj_dismantle.in", "r", stdin);
	freopen("cspjx2019pj_dismantle.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &a1, &a2);
		b[a1].push_back(a2);
		b[a2].push_back(a1);
	}
	scanf("%d%d%d%d", &S1, &T1,&S2, &T2);
	memset(dis1, 0x3f3f3f3f, sizeof(dis1));
	memset(dis2, 0x3f3f3f3f, sizeof(dis2));
	memset(dis3, 0x3f3f3f3f, sizeof(dis3));
	DIJ(1, dis1);
	DIJ(S1, dis2);
	DIJ(S2, dis3);
	int minn = 998244353;
	for (int i = 1; i <= n; i++)
	{
		if (dis1[i] + dis2[i] <= T1 && dis1[i] + dis3[i] <= T2)
		{
			minn = min(minn, dis1[i] + dis2[i] + dis3[i]);
		}
	}
	if (minn == 998244353)
	{
		printf("-1");
		return 0;
	}
	printf("%d", m - minn);
	return 0;
}