#include<bits/stdc++.h>
using namespace std;
int m,n;
int l1,t1,t2,l2;
int tot=INT_MAX,l=0;
struct City{
    vector<int> d;
};
City c[35001];
int N[35001][2];
vector<int> way;
void qwe(int x,int time,int last,int lasttime)
{
    if(time>lasttime||time>N[x][0])  return; 
    N[x][0]=time;  
    N[x][1]=time-l; 
    int a=0;
    for(int i=0;i<c[x].d.size();++i)
    {
        bool flag=true;
        for(int j=0;j<way.size()-1;++j)
            if((way[j]==x&&way[j+1]==c[x].d[i])||
            (way[j+1]==x&&way[j]==c[x].d[i]))
            {
                l++;
                flag=false;
                break;
            }
        qwe(c[x].d[i],time+1,last,lasttime);
        if(flag==false)l--;
    }
    return;
}
void asd(int x,int time,int last,int lasttime)
{
    if(time>lasttime) return;   
    if(x==last)
    {
        for(int i=1;i<=n;++i)
        N[i][0]=INT_MAX;
        l=0;
        qwe(1,0,l2,t2);
        tot=min(tot,N[l2][1]+time-l);
        return;
    }
    for(int i=0;i<c[x].d.size();++i)
    {
        way.push_back(c[x].d[i]);
        asd(c[x].d[i],time+1,last,lasttime);
        way.pop_back();
    }
    return;
}
int main()
{
    freopen("cspjx2019pj_dismantle.in","r",stdin);
    freopen("cspjx2019pj_dismantle.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        c[a].d.push_back(b); c[b].d.push_back(a);
    }
    cin>>l1>>t1>>l2>>t2;
    way.push_back(1);
    asd(1,0,l1,t1);
    if(N[l2][0]==INT_MAX) cout<<-1;
    else cout<<m-tot;
    return 0;
}