#include<iostream>
#include<fstream>
# define nmax 50001
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n,m,s,i,v,x,y,a[nmax][10000],pa[nmax],p,u,d,c[nmax],viz[nmax];
int main()
{

    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][0]++;
        a[x][a[x][0]]=y;
          }
    for (i=1;i<=n;i++)
        pa[i]=-1;
    p=u=1; pa[s]=0;
    c[p]=s;
    viz[s]=1;
    while(p<=u)
    {
    x=c[p];
    //cautam vf adiacente
    for(i=1;i<=a[x][0];i++)
            {
               v=a[x][i];
          if(viz[v]==0){
          u++;
          c[u]=v;
          viz[v]=1;
          pa[v]=pa[x]+1;
                     }
            }
      p++;
     }
    for(i=1;i<=n;i++)
        g<<pa[i]<<" ";
        g<<endl;
    return 0;
}