#include<fstream>
using namespace std;
ifstream fi("bfs.in");
ofstream fo("bfs.out");
long long int n,m,x,y,z,u,coada[100005],viz[100005],c[100005];
struct nod{
       int info;
       nod* back;
       };
nod* v[100005];
void add(int i,int j){
     nod* c=new nod;
     c->info=j;
     c->back=v[i];
     v[i]=c;
}
void bfs(int i){
     for(nod* p=v[coada[i]];p!=NULL;p=p->back)
        if(!viz[p->info]){
                          viz[p->info]=1;
                          u++;
                          coada[u]=p->info;
                          c[p->info]=i;
         }
         if(i<u) bfs(i+1);
}
int main(){
    fi>>n>>m>>z;
    for(int i=1;i<=m;i++){
            fi>>x>>y;
            add(x,y);
            }
    u=1;
    coada[1]=z;
    viz[z]=1;
    bfs(1);
    for(int i=1;i<=n;i++)
    if(!viz[i]) fo<<"-1 ";
    else
    fo<<c[i]<<" ";
    
    
    
    return 0;
    }