#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

ifstream x("bfs.in");
ofstream y("bfs.out");

int n,m,s,i,j,k,viz[100002],c[100002],pi,ps,a[10002][10002],cost[100002];

int main()
{
    x>>n>>m>>s;
    for(k=1;k<=m;k++)
    {
        x>>i>>j;
        a[i][j]=1;
    }
    c[1]=s;
    viz[s]=1;
    pi=ps=1;
    memset(cost,-1,sizeof(cost));
    cost[s]=0;
    while(ps<=pi)
    {
        k=c[ps];
        for(i=1;i<=n;i++)
            if(a[k][i]==1 && viz[i]==0 && i!=k)
                pi++,c[pi]=i,viz[i]=1,cost[c[pi]]=cost[c[ps]]+1;
        ps++;
    }
    for(i=1;i<=n;i++)
        y<<cost[i]<<" ";
    x.close();
    y.close();
    return 0;
}