#include <fstream>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
typedef struct celula
{
    int nod;
    celula *  pred;
}  * lista;

lista gr[100010],v;
int n,m,s,used[100010],drum[100010],coada[100010],i,x,y;
int main()
{
    cin>>n>>m>>s;
    for (i=1;i<=m;i++)
        cin>>x>>y, v= new celula, v->nod=y, v->pred=gr[x], gr[x]=v;
    for (i=1;i<=n;i++) drum[i]=-1, used[i]=0;
    int p=1,u=1;
    coada[p]=s;
    used[s]=1;
    drum[s]=0;



    while (p<=u)
    {
        int q=coada[p];
        p++;
        v= new celula; v=gr[q];
        while (v)
        {
            if (!used[v->nod])
            {
                used[v->nod]=1;
                coada[++u]=v->nod;
                drum[v->nod]=drum[q]+1;
            }
            v=v->pred;
        }
    }
    for (i=1;i<=n;i++) cout<<drum[i]<<" ";
    return 0;
}