#include <iostream>
#include <fstream>

#define nMax 100001

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n, m, S, viz[nMax], coada[nMax];

struct lista
{
    int val;
    lista *nxt;
};

void insertFront(lista * &hd, int v)
{
    lista *elem=new lista;
    elem->val=v;
    elem->nxt=hd;
    hd=elem;
}

int main()
{
    int a, b;
    fin>>n>>m>>S;
    lista *head[nMax]={NULL};

    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        insertFront(head[a], b);
    }

    int st=1, dr=0;
    for(int i=1; i<=n; i++)
        viz[i]=-1;
    viz[S]=0;
    coada[++dr]=S;
    while(st<=dr)
    {
        int node=coada[st++];
        lista *nod=head[node];
        while(nod!=NULL)
        {
            if(viz[nod->val]==-1)
            {
                viz[nod->val]=viz[node]+1;
                coada[++dr]=nod->val;
            }
            nod=nod->nxt;
        }
    }

    for(int i=1; i<=n; i++)
        fout<<viz[i]<<" ";
}