#include <fstream>
#include <iostream>
using namespace std;


int n,m, mat[10000][10000], s, viz[10000];

void citire()
{
    freopen("bfs.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &s);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        mat[a][b] = 1;
    }
    for(int i=1;i<=n;i++)
        viz[i] = -1;
}

void bfs()
{
    int p = 0,u =0, c[10000];
    c[0] = s;
    int nr = 1;
    viz[s] = 0;
    int l = u;
    while(p<=u)
    {
        int v = c[p];
        if(l < u)
            {
                nr++;
                l = u;
            }
        for(int k=1;k<=n;k++)
            if(mat[v][k] == 1 && viz[k] == -1)
            {
                u++;
                c[u] = k;
                viz[k] = nr;
            }
        p++;
    }

}

void afisare()
{
    freopen("bfs.out", "w", stdout);
    for(int i=1;i<=n;i++)
    {
        printf("%d ", viz[i]);
    }
}
int main()
{
    citire();
    bfs();
    afisare();

    return 0;
}