#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int A[100001];
int s;
struct nod
{
    nod *bck=0;
    int val;
}*v[100001],*inceput,*sfarsit;
int n,m,a,b;
nod *c;
void citire()
{
    fin>>n>>m>>s;
    inceput=new(nod);
    sfarsit=new(nod);
    inceput->val=s;
    inceput->bck=sfarsit;
    sfarsit->val=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=new(nod);
        v[i]->val=0;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        c=new(nod);
        c->val=b;
        c->bck=v[a];
        v[a]=c;
    }
}
void bfs()
{
    int y;
    int x=inceput->val;
    while(x!=0)
    {
        while(v[x]->val!=0)
        {
            y=v[x]->val;
            if(A[y]==0 and y!=s and y!=x)
            {
                sfarsit->val=y;
                c=new(nod);
                c->val=0;
                sfarsit->bck=c;
                sfarsit=c;
                A[y]=A[x]+1;
            }
            v[x]=v[x]->bck;
        }
        inceput=inceput->bck;
        x=inceput->val;
    }
}
int main()
{
    citire();
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(A[i]==0 and i!=s) fout<<"-1 ";
        else fout<<A[i]<<" ";
    }
}