#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,k,i,j,x,c[100005],viz[100005];

struct nod{int info;
           nod* urm;}*prim[100005];

void BFS(int x)
{
  viz[x]=1;
  c[1]=x;
  int p=1,u=1;
  nod *q;
  while(p<=u){
    //ADAUG IN COADA TOTI VECINII NEVIZITATI
    q=prim[x];
    while(q){
        if(!viz[q->info]){
            c[++u]=q->info;
            viz[q->info]=p;
        }
        q=q->urm;
    }
    ++p;
    x=c[p];
  }
}

void adauga(int x, int y) //il adaug pe x in lista lui y
{
    nod *p;
    p=new nod;
    p->info=x;
    p->urm=prim[y];
    prim[y]=p;
}

void afis()
{
    for(int i=1;i<=n;++i){
        if(i==x)fout<<0<<' ';
        else if(!viz[i])fout<<"-1 ";
             else fout<<viz[i]<<' ';
    }
    fout<<'\n';
}

int main()
{
    fin>>n>>m>>x;
    for(k=1;k<=m;++k){
        fin>>i>>j;
        adauga(j,i);
    }
    BFS(x);
    afis();
   /*nod *p;
   for(i=1;i<=n;++i){
    fout<<i<<": ";
    p=prim[i];
    while(p){
        fout<<p->info<<' ';
        p=p->urm;
    }
    fout<<'\n';
   }*/

    fin.close(); fout.close();
    return 0;
}