#include<stdio.h>
#include<list>
#include<cstring>

bool vizitat[100001];

std::list<int> *l;
std::list<int> q;
std::list<int> cost;
FILE *fin,*fout;
int mi[100001];

void bfs()
{
    /*if(mi[q.back()]>cost.back()||mi[q.back()]==-1)
    {
        mi[q.back()]=cost.back();
    }
    while(!l[q.back()].empty()&&vizitat[q.back()]==0)
    {
        q.push_front(l[q.back()].back());
        cost.push_front(cost.back()+1);
        l[q.back()].pop_back();
    }
    vizitat[q.back()]=1;
    q.pop_back();
    cost.pop_back();
    if(!q.empty())
    {
        bfs();
    }*/

    while(!q.empty())
    {
        if(mi[q.back()]>cost.back()||mi[q.back()]==-1)
        {
            mi[q.back()]=cost.back();
        }
        while(!l[q.back()].empty())
        {
            if(vizitat[l[q.back()].back()]==0)
            {
                q.push_front(l[q.back()].back());
                cost.push_front(cost.back()+1);
            }
            l[q.back()].pop_back();
        }
        vizitat[q.back()]=1;
        q.pop_back();
        cost.pop_back();
    }
}

int main()
{
    std::memset(mi, -1, sizeof(mi));

    fin=fopen("bfs.in","r");
    fout=fopen("bfs.out","w");

    int n,m,s,t1,t2;
    fscanf(fin,"%d %d %d",&n,&m,&s);

    l=new std::list<int>[n+1];

    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d",&t1,&t2);
        l[t1].push_front(t2);
    }

    cost.push_back(0);
    q.push_front(s);
    bfs();

    for(int i=1;i<=n;i++)
    {
        fprintf(fout,"%d ",mi[i]);
    }
}