#include <bits/stdc++.h>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
const int N = 100010;
struct nl
{
    int inf;
    nl *nxt;
};
int n,m,s,d[N],lo,hi;
nl *v[N],*aux;
int q[N];
int main ()
{
    f>>n>>m>>s;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        f>>x>>y;
        aux=new nl;
        aux->inf=y;
        aux->nxt=v[x];
        v[x]=aux;
    }
    d[s]=1;
    lo=hi=1;
    q[lo]=s;
    while(lo<=hi)
    {
        int nod=q[lo++];
        for(aux = v[nod]; aux != NULL ; aux = aux -> nxt)
            if(!d[aux->inf])
            {
                d[aux->inf]=d[nod]+1;
                q[++hi]=aux->inf;
            }
    }
    for(int i=1; i<=n; i++)
        g<<d[i]-1<<' ';
    return 0;
}