#include <fstream>
#include <string.h>

using namespace std;

struct nod
{
    int info;
    nod *next;
}   *prim[100001], *aux, *p;

int v[100007], drum[100007], q[100007];

int main()
{
    ifstream in ("bfs.in");
    ofstream out ("bfs.out");
    int n, m, s, i, a, b;
    in>>n>>m>>s;
    for (i=1; i<=m; i++)
    {
        in>>a>>b;
        if (a!=b)
        {
            aux=new nod;
            aux->info=b;
            aux->next=prim[a];
            prim[a]=aux;
        }
    }
    int l=1, f=1;
    memset (drum, -1, sizeof(drum));
    v[s]=1;
    drum[s]=0;
    q[1]=s;
    while (f<=l)
    {
        for (p=prim[q[f]]; p; p=p->next)
            if (v[p->info]==0)
            {
                v[p->info]=1;
                drum[p->info]=drum[q[f]]+1;
                q[++l]=p->info;
            }
        f++;
    }
    for (i=1; i<=n; i++)
        out<<drum[i]<<" ";
    return 0;
}