#include<fstream.h>

#define xn 100001
#define xm 1000001

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct lista{ int nod; lista *urm;} *g[xn];
int m,n,s,t[xn],q[xn];

int main()
{
    memset(t,-1,sizeof(t));
    fin>>n>>m>>s;
    lista *p;
    int x,y,i,nod,li,ls;
    
    for(i=1;i<=n;i++)
    {
       fin>>x>>y;              
       p=new lista;
       p->nod=y;
       p->urm=g[x];
       g[x]=p;
    }
    
    li=ls=1;
    q[li]=s;
    t[s]=0;
    
    for(;li<=ls;li++)
    {
      nod=q[li];
      for(p=g[nod];p;p=p->urm)
        if(t[p->nod]!=-1)
        {
          q[++li]=p->nod;
          t[p->nod]=nod;
        }
    }
    
    for(i=1;i<=n;i++)
      fout<<t[i]<<' ';
    fout<<'\n';
    
    fout.close();
    return 0;
}