题目：

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

输入
单组测试数据。
第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n*(n-1)/2) )。
接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。
输入保证是一个连通图。
最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。

输出
输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。

输入样例
5 4
1 2
2 3
3 4
4 5
1 3 2
3 5 2

输出样例
0

题目要我们删除最多的道路，我们可以转化为：留下最少的道路。

如果两条路径不相交，那么留下最少的道路就是，分别两个的最短路之和。

但是如果相交呢？我们枚举每一条路径，求出最大相交的路径即可。

我们枚举 i->j 的路径，然后就会有两种情况，s1->i->j->t1,s2->i->j->t2和s1->i->j->t1,s2->j->i->t2这两种情况，分别取min即可。

还有这道题，因为是稀疏图，所以我们用spfa求两点之间的最短路，用Dijkstra会TLE。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3010;
int n,m,s1,t1,l1,s2,t2,l2,res,d[N][N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void spfa(int s){
	queue<int> q;	q.push(s);	d[s][s]=0;	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(d[s][to[i]]>d[s][u]+1){
				d[s][to[i]]=d[s][u]+1;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
}
signed main(){
	cin>>n>>m; memset(d,0x3f,sizeof d);
	for(int i=1,a,b;i<=m;i++)	cin>>a>>b,add(a,b),add(b,a);
	cin>>s1>>t1>>l1>>s2>>t2>>l2;
	for(int i=1;i<=n;i++)	spfa(i);
	if(d[s1][t1]>l1||d[s2][t2]>l2)	return puts("-1"),0;
	res=d[s1][t1]+d[s2][t2];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(d[s1][i]+d[i][j]+d[j][t1]<=l1&&d[s2][i]+d[i][j]+d[j][t2]<=l2)
				res=min(res,d[i][j]+d[s1][i]+d[j][t1]+d[s2][i]+d[j][t2]);
			if(d[s1][i]+d[i][j]+d[j][t1]<=l1&&d[s2][j]+d[j][i]+d[i][t2]<=l2)
				res=min(res,d[i][j]+d[s1][i]+d[j][t1]+d[s2][j]+d[i][t2]);
		}
	}
	cout<<m-res<<endl;
	return 0;
}