//lee
#include<fstream>
 using namespace std;
 ifstream in("alee.in");
 ofstream out("alee.out");
 short a[176][176],n,m,prt[5];
 typedef struct
 {
 unsigned short c1,c2,lung;
 } coada;
 coada c[999999];
 void citire()
 {
 short i,p,q;
 in>>n>>m;
 for(i=1;i<=2*m;i=i+2)
 {in>>q>>p;
 a[q][p]=2;
 }
 for(i=1;i<=4;i++)
 in>>prt[i];
 c[1].c1=prt[1];
 c[1].c2=prt[2];
 c[1].lung=1;
 }
 void creare_matrice()
 {
 unsigned short i,j;
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 if (a[i][j]!=2)
 a[i][j]=0;

 }
 int test_vecini(int i,int j)
 {
 if(i>=1 && i<=n && j>=1 && j<=n)
 return 1;
 return 0;
 }
 int main()
 {
 unsigned short i,j,k=2,p=1;
 citire();
 creare_matrice();
 while(p<k)
 {
 i=c[p].c1;
 j=c[p].c2;
 if( i==prt[3] && j==prt[4] )
 {
 out<<c[p].lung;
 return 0;

 }
 if((a[i+1][j]==0) && test_vecini(i+1,j))
 { a[i+1][j]=5;
 c[k].c1=i+1;
 c[k].c2=j;
 c[k].lung=c[p].lung+1;
 k++;
 }
 if((a[i][j+1]==0) && test_vecini(i,j+1))
 { a[i][j+1]=5;
 c[k].c1=i;
 c[k].c2=j+1;
 c[k].lung=c[p].lung+1;
 k++;
 }
 if((a[i][j-1]==0) && test_vecini(i,j-1))
 { a[i][j-1]=5;
 c[k].c1=i;
 c[k].c2=j-1;
 c[k].lung=c[p].lung+1;
 k++;
 }
 if((a[i-1][j]==0) && test_vecini(i-1,j))
 { a[i-1][j]=5;
 c[k].c1=i-1;
 c[k].c2=j;
 c[k].lung=c[p].lung+1;
 k++;
 }
 p++;
 }
 }


//bfs#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define NMAX 1000002
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
vector <int> v[NMAX];
int n,S,viz[NMAX],c[NMAX];
long m;
void read()
{
int x,y,i;
in>>n>>m>>S;
for( i=1; i<=m; i++)
{ in>>x>>y;
v[x].push_back(y);
}
}
int main ()
{
int p,k,j,i;
read();
p=k=1;
c[p]=S;
viz[S]=0;
while(p<=k)
{
for(j=0;j<v[c[p]].size();++j)
if(viz[v[c[p]][j]]==0 && v[c[p]][j]!=S )
{
c[++k]=v[c[p]][j];
viz[v[c[p]][j]]=viz[c[p]]+1;
}
p++;
}
for(i=1;i<=n;i++)
if(viz[i]==0 && i!=S)
out<<-1<<" ";
else
out<<viz[i]<<" ";
in.close();
out.close();
return 0;
}


//dfs
#include<fstream>
#include<iostream>
#include<vector>
#define MMAX 200002
#define NMAX 100002
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector <int> v[MMAX];
int n,m;
bool viz[NMAX];
void read ()
{
in>>n>>m;
int x,y;
for(int i=1; i<=m; i++)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void dfs(int nod)
{
viz[nod]=1;
for(int i=0; i<v[nod].size(); ++i )
if(viz[v[nod][i]]==0)
dfs(v[nod][i]);
}
int main ()
{
int p=1;
read();
dfs(1);
for(int i=2; i<=n; ++i)
if(viz[i]==0)
{
dfs(i);
p++;
}
out<<p ;
in.close();
out.close();
return 0;
}

//DIJKSTRA
#include<fstream>
#include<cstdio>
#define INF=99999
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct graf
{
int nod,cost;
graf *next;
};
graf *a[50001];
int d[50001],viz[50001],n,m;
void add (int loc, int nodaferent,int cost)
{
graf *q;
q=new graf;
q->nod=nodaferent;
q->cost=cost;
q->next=a[loc];
a[loc]=q;
}
void read()
{
int x,y,z;
in>>n>>m;
for(int i=1; i<=m; i++)
{ in>>x>>y>>z;
add(x,y,z);
}
}
void dijkstra ()
{
for(int i=2; i<=n; i++)
{ d[i]=999999;
// tata[i]=1;
}
int min,k=0;
for(int j=1; j<=n;j++)
{ min=999999;
for(int i=1; i<=n; i++)
if(min>d[i] && !viz[i])
{
min=d[i];
k=i;
}
viz[k]=1;
graf *t=a[k];
while(t)
{ if(d[t->nod]>d[k]+t->cost)
d[t->nod]=d[k]+t->cost;
// tata[t->nod]=k;
t=t->next;
}
}
}
int main ()
{
read();
dijkstra();
for(int i=2; i<=n; i++)
if(d[i]==999999)
out<<0<<" " ;
else
out<<d[i]<<" " ;
in.close();
out.close();
return 0;
}