#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
int q[100009],i,j,sel[100009],lg[100009],n,m,s,x,y;
vector<int> G[100009];

void bfs(int pl)
{
  int p,u,x;
  vector<int> :: iterator it;
  sel[pl]=true;
  p=u=1;
  q[1]=pl;
  lg[pl]=0;
  while(p<=u)
  {
     x=q[p];
     for(it=G[x].begin();it!=G[x].end();++it)
     if(!sel[*it])
     {
        q[++u]=*it;
        sel[*it]=true;int k=*it;
        lg[k]=lg[x]+1;
     }

    ++p;
}
}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);

    scanf("%d%d%d",&n,&m,&s);

    for(i=1;i<=m;++i)
    {
       scanf("%d%d",&x,&y);
       G[x].push_back(y);

    }

    memset(lg,-1,sizeof(lg));
    bfs(s);

    for(i=1;i<n;++i)
    printf("%d ",lg[i]);

    printf("%d\n",lg[n]);


    return 0;
}