#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int  inf =0x7f7f7f7f;

const double pi=acos(-1);

const int maxn=3000;

vector<int> G[maxn+5];

int n,m,used[maxn+10],dist[maxn+10][maxn+10],vis[maxn+10];

void bfs(int s)

{

     MM(used,0);

     MM(vis,0);

     fill(dist[s]+1,dist[s]+n+1,inf);

     queue<int> q;

     q.push(s);

     dist[s][s]=0;

     used[s]=1;

     vis[s]=1;

     while(q.size())

     {

         int u=q.front();q.pop();

         used[u]=1;

         for(int i=0;i<G[u].size();i++)

         {

             int v=G[u][i];

             if(used[v]) continue;

             dist[s][v]=min(dist[s][v],dist[s][u]+1);

             if(!vis[v])  {q.push(v);vis[v]=1;}

         }

     }

}

int main()

{

    while(~scanf("%d %d",&n,&m))

    {

        for(int i=1;i<=n;i++) G[i].clear();

        for(int i=1;i<=m;i++)

        {

            int u,v;

            scanf("%d %d",&u,&v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

        int s1,t1,l1,s2,t2,l2;

        scanf("%d %d %d %d %d %d",&s1,&t1,&l1,&s2,&t2,&l2);

        for(int i=1;i<=n;i++)

            bfs(i);

        if(dist[s1][t1]>l1||dist[s2][t2]>l2)

        {

            printf("-1\n");

            continue;

        }

        int ans=dist[s1][t1]+dist[s2][t2];

        for(int u=1;u<=n;u++)

           for(int v=1;v<=n;v++)

           {

              if(dist[s1][u]+dist[u][v]+dist[v][t1]<=l1&&dist[s2][u]+dist[u][v]+dist[v][t2]<=l2)

                 ans=min(ans,dist[s1][u]+dist[u][v]+dist[v][t1]+dist[s2][u]+dist[v][t2]);

              if(dist[s1][u]+dist[u][v]+dist[v][t1]<=l1&&dist[s2][v]+dist[v][u]+dist[u][t2]<=l2)

                 ans=min(ans,dist[s1][u]+dist[u][v]+dist[v][t1]+dist[s2][v]+dist[u][t2]);

           }

           printf("%d\n",m-ans);

    }

    return 0;

}