#include <bits/stdc++.h>
#define maxn 3005
using namespace std;
int head[maxn],vis[maxn],dis[maxn],tot,n,m;
int last[maxn],way1[maxn],way2[maxn];
int cnt[maxn],ans,t1,t2;
struct Edge{
	int to,nex;
}e[maxn<<1];
struct pos{
	int x,steps;
}cur,nex;
void add(int x,int y){
	e[++tot].to=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
queue<pos> que;
void bfs(){
	memset(vis,0,sizeof(vis));
	vis[1]=1; dis[1]=0;
	cur.x=1; cur.steps=0; last[1]=0;
	que.push(cur);
	while(!que.empty()){
		cur=que.front();
		que.pop();
		for(int i=head[cur.x];i;i=e[i].nex){
			int to=e[i].to;
			if(!vis[to]){
				nex.x=to; nex.steps=cur.steps+1; last[to]=cur.x;
				que.push(nex); vis[to]=1; dis[to]=nex.steps;
			}
		}
	}
}
void BFS(int start,int target,int step,int op,int S){
	memset(vis,0,sizeof(vis));
	vis[start]=1; 
	cur.x=start; cur.steps=step; 
	que.push(cur);
	while(!que.empty()){
		cur=que.front();
		que.pop();
		if(op==1)
			if(cur.steps-step+S>t1) return;
		if(op==2)
			if(cur.steps-step+S>t2) return;
		if(cur.x==target){
			ans=min(ans,cur.steps);
			return;
		}
		if(cur.steps>=ans) return;
		for(int i=head[cur.x];i;i=e[i].nex){
			int to=e[i].to;
			if(!vis[to]){
				nex.x=to; nex.steps=cur.steps+1; 
				que.push(nex); vis[to]=1; 
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int x,y,s1,s2,len,tmp;
	while(cin>>n>>m){
		for(int i=1;i<=m;i++) 
			cin>>x>>y,add(x,y),add(y,x);
		cin>>s1>>t1>>s2>>t2;
		bfs();
		if(dis[s1]>t1||dis[s2]>t2){
			cout<<"-1"<<endl;
			continue;
		}
		len=1; tmp=s1; way1[1]=s1;
		while(last[tmp]!=0){
			way1[++len]=last[tmp];
			tmp=last[tmp];
		}way1[++len]=1;
		len=1; tmp=s2; way2[1]=s2;
		while(last[tmp]!=0){
			way2[++len]=last[tmp];
			tmp=last[tmp];
		}way2[++len]=1;
		memset(cnt,0,sizeof(cnt)); tmp=0;
		for(int i=1;i<=dis[s1]+1;i++) cnt[way1[i]]=1;
		for(int i=1;i<=dis[s2]+1;i++) 
			if(cnt[way2[i]]) cnt[way2[i]]=2,tmp++;
		ans=dis[s1]+dis[s2]-tmp+1;
		for(int i=1;i<=dis[s1];i++){
			if(cnt[way1[i]]==2) continue;
			BFS(way1[i],s2,dis[s1],2,dis[s1]-i+1);
		}
		for(int i=1;i<=dis[s2];i++){
			if(cnt[way2[i]]==2) continue;
			BFS(way2[i],s1,dis[s2],1,dis[s2]-i+1);
		}
		cout<<m-ans<<endl;
	}
	return 0;
}

代码是自己瞎写的，若丑不要介意