#include <iostream>
#include <stdio.h>
#include <queue>
#define MAX 100001

using namespace std;

struct nod{
    int info;
    nod* next;
};

nod *G[MAX];

void add_nod(int a, int b)
{
    nod *p = new nod;
    p->info = b;
    p->next = G[a];
    G[a] = p;
}

int M, N, S;

void citire()
{
    int a, b;
    scanf("%d %d %d",&N,&M,&S);
    for(int i = 1; i <= M; i++)
    {
        scanf("%d %d",&a,&b);
        add_nod(a,b);
    }
}

int D[MAX];

void solve()
{
    queue<int> Q;
    int t;
    Q.push(S);
    D[S] = 1;
    while(!Q.empty())
    {
        t = Q.front();
        nod *p;
        p = G[t];
        while(p)
        {
            if(!D[p->info])
            {
                D[p->info] = D[t] + 1;
                Q.push(p->info);
            }
            p = p->next;
        }
        Q.pop();
    }
}

void ecrire()
{
    for(int i = 1; i <= N; i++)
        printf("%d ", D[i]-1);

}

int main()
{
    freopen ("bfs.in","r",stdin);
    freopen ("bfs.out","w",stdout);
    citire();
    solve();
    ecrire();
    return 0;
}