#include <iostream>
#include <stdio.h>
#include <deque>
#include <bitset>
#define maxim 999999
using namespace std;
FILE *f,*g;
deque <int> q;
bitset <100002> been;
int a[2][1000002],start[100002],cost[100002];
int n,m,k,s;
void read()
{
    int x,y,c;
    fscanf(f,"%d %d %d",&n,&m,&s);
    for(int i=1; i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        k++;
        a[0][k]=y;
        a[1][k]=start[x];
        start[x]=k;
    }
}
void BFS()
{
    for(int i=1; i<=n; i++)
        cost[i]=maxim;
    q.push_back(s);
    been[s]=1;
    cost[s]=0;
    while(!q.empty())
    {
        int node=q.front();
        q.pop_front();
        int ok=start[node];
        int x=cost[node];
        while(ok)
        {
            if(!been[a[0][ok]] || cost[a[0][ok]]>x+1)
            {
                q.push_back(a[0][ok]);
                cost[a[0][ok]]=x+1;
                been[a[0][ok]]=1;
            }
            ok=a[1][ok];
        }
    }
}
void write()
{
    for(int i=1; i<=n; i++)
    {
        if(cost[i]==maxim)
            fprintf(g,"-1 ");
        else
            fprintf(g,"%d ",cost[i]);
    }
}
int main()
{   int p;
    f=fopen("bfs.in","r");
    g=fopen("bfs.out","w");
    read();
    BFS();
    write();

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