#include <fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
int T[2][1000005],start[100005],coada[100005],d[100005],p=1,u;
int main()
{
    int k=0,n,m,s,l,i,j;
    in>>n>>m>>s;
    for(i=1;i<=n;i++)
        d[i]=-1;
    for(l=1;l<=m;l++)
    {
     in>>i>>j;
     T[0][++k]=j;
     T[1][k]=start[i];
     start[i]=k;
    }
    coada[++u]=s;
    d[s]=0;
    while(p<=u)
    {
     for(i=start[coada[p]];i>0;i=T[1][i])
     {
      if(d[T[0][i]]==-1)
      {
       d[T[0][i]]=d[coada[p]]+1;
       coada[++u]=T[0][i];
      }
     }
     p++;
    }
    for(i=1;i<=n;i++)
        out<<d[i]<<" ";
    return 0;
}