# include <iostream>
# include <fstream>
using namespace std;
fstream f("bfs.in",ios::in);
fstream g("bfs.out",ios::out);
int a[10000][10000],x,y,s,c[10000],n,m,i,p,pas[10000],viz[10000],u;
int main()
{
f>>n>>m>>s;
for (i=1;i<=n;i++)
   pas[i]=-1;
for (i=1;i<=m;i++)
{
f>>x>>y;
a[x][y]=1;
}
p=u=1;
c[p]=s;
viz[s]=1;
;pas[s]=0;
while (p<=u)
{
x=c[p];
for (i=1;i<=n;i++)
if (a[x][i]==1 && viz[i]==0)
{
u++;
c[u]=i;
viz[i]=1;
pas[i]=pas[x]+1;
}
p++;
}
//for (i=1;i<=u;i++)
//if(viz[i]==0) pas[i]=-1;
for (i=1;i<=n;i++)
g<<pas[i]<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}