#include <fstream>
#include<string.h>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int a[1001][1001],n,m,s,x,y;
int q[100001],cost[100001],p,u;
void add_vecini(int el);
bool viz[100001];
int main()
{
    //a[i][j]=el din a[i][j] este vecin al lui i
    //a[i][0]=nr de vecini
    f>>n>>m>>s;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        a[x][++a[x][0]]=y;
    }
    //add s
    memset(cost,-1,sizeof(cost));
    q[1]=s;
    cost[s]=0;
    viz[s]=1;
    p=u=1;
    while(p<=u){
            add_vecini(q[p]);
            p++;
    }
    for(int i=1;i<=n;i++)
        g<<cost[i]<<' ';
    return 0;
}


void add_vecini(int el){
    for(int i=1;i<=a[el][0];i++){
        if(viz[a[el][i]]==0){
            viz[a[el][i]]=1;
            q[++u]=a[el][i];
            cost[a[el][i]]=cost[q[p]]+1;
        }
    }
}