RT

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define N 3001
using namespace std;
//
int sum[N],sum1[N],dis[N];
int minn=0x7fffffff,n,m;
bool used[N],jud;
struct node
{
	int dot,num;
	bool operator<(const node &x)const{x.num<num;}
};
priority_queue<node> h;
vector<int> data[N];

//

inline void dij(int ori)
{
	for(int i=1;i<=n;++i)
	{
		dis[i]=0x7fffffff-1;
		used[i]=0;
	}
	jud=0;dis[ori]=0;
	node res;res.dot=ori;
	h.push(res);
    while(!h.empty())
    {
    	node res=h.top();
    	int u=res.dot;h.pop();
//    	cout<<u<<endl;
    	if(used[u]&&jud!=0)continue;
    	jud=1;
    	for(int i=0;i<data[u].size();++i)
    	{
    		int v=data[u][i];
    		if(dis[u]+1<dis[v])
    		{
//    			cout<<"cynb!";
    			dis[v]=dis[u]+1;
    			res.num=dis[v];
    			res.dot=v;
    			h.push(res);
			}
		}
		used[u]=1;
	}
}

//

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int x,y;cin>>x>>y;
		data[x].push_back(y);
		data[y].push_back(x);
	}
	int x1,t1,x2,t2;
	cin>>x1>>t1>>x2>>t2;
    dij(1);
    for(int i=1;i<=n;++i)sum[i]=dis[i];
    dij(x1);
    for(int i=1;i<=n;++i)
	sum1[i]=dis[i];
    dij(x2);
    for(int i=1;i<=n;++i)
    {
	    if(sum1[i]+sum[i]<=t1)
    	if(sum[i]+dis[i]<=t2)
    	{
    		minn=min(sum[i]+sum1[i]+dis[i],minn);
		}
	}
	if(minn==0x7fffffff)
	{
		cout<<-1;return 0;
	}
	cout<<(m-minn);
	return 0;
}