#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int m, n, x, y, R, viz[100001], k, nr[100001];
struct nod
{
    int info;
    nod *next;
}*p[100001], *u[100001], *psol, *usol;
void adauga(nod *&p, nod *&u, int x)
{
    nod *c = new nod;
    c->info = x;
    c->next = 0;
    if(p==0)
    {
        p=c;
        u=c;
    }
    else
    {
        u->next = c;
        u = c;
    }
}
void bfs()
{
    for(nod *q=psol; q!=NULL; q=q->next)
    {
        for(nod *c=p[q->info]; c!=NULL; c=c->next)
        {
            if(viz[c->info]==0)
            {
                nr[c->info]=nr[q->info]+1;
                viz[c->info]=1;
                adauga(psol, usol, c->info);
            }
        }
    }
}
int main()
{
    fin>>n>>m>>R;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        adauga(p[x], u[x], y);
    }
    adauga(psol, usol, R);
    viz[R]=1;
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(nr[i]==0)
        {
            nr[i]=-1;
        }
    }
    nr[R]=0;
    for(int i=1;i<=n;i++)
    {
        fout<<nr[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}