#include <fstream>
#include <iostream>
using namespace std;
ifstream f ("bfs.in");
ofstream g ("bfs.out");
int v[1003][1003],coada[10003],n,m,s,a,b,st,dr,sol[1003],nod;
int main()
{
    f>>n>>m>>s;
    for(int i=1;i<=m;++i)
    {
        f>>a>>b; //din a pot ajunge in b
        v[a][b]=1;
    }
    coada[1]=s; //primul elem din coada e sursa
    st=dr=1; //indicii cu care se plimba coada
    for(int i=1;i<=n;++i) sol[i]=-1; //presupunem toate elementele nevizitabile
    sol[s]=0; //din sursa esti in sursa
    while(st<=dr) //cat timp ai elemente in coada
    {
        nod=coada[st]; //nodul actual din coada
        ++st; //scoti nodul din coada
        for(int i=1;i<=n;++i) //cauti noduri care sunt vecini
        {
            if(!v[nod][i]) continue; //daca nu ai muchie
            if(sol[i]!=-1) continue; //daca deja ai vizitat nodul
            sol[i]=sol[nod]+1;
            ++dr;
            coada[dr]=i;
        }
    }
    for(int i=1;i<=n;++i) g<<sol[i]<<' ';
    return 0;
}