#include <stdio.h>
#include <vector>
#include <deque>


using namespace std;
FILE *f,*g;

vector <int> v[100002];
deque <int> q;
int drum[100009];
bool viz[1000009];

int main()
{
    int n,m,i,nod,x,y,ok=0,j,no,dr,vecin;
    f=fopen("bfs.in","r");
    g=fopen("bfs.out","w");
    fscanf(f,"%d %d %d",&n,&m,&nod);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d",&x,&y);
        v[x].push_back({y});
    }
    for(i=1;i<=n;++i)
        drum[i]=2000000000;
    drum[nod]=0;
    q.push_back({nod});
    while(!q.empty())
    {
        no=q.front();
        q.pop_front();
        if(viz[no]==0)
        {
            for(j=0;j<v[no].size();++j)
            {
                dr=drum[no];
                vecin=v[no][j];
                if(dr+1<drum[vecin])
                {
                    drum[vecin]=dr+1;
                    q.push_back({vecin});
                }
            }
        }
        viz[no]=1;
    }
    for(i=1;i<=n;++i)
    {
        if(drum[i]==2000000000)
            fprintf(g,"-1 ");
        else
            fprintf(g,"%d ",drum[i]);
    }


    fclose(f);
    fclose(g);
    return 0;
}