//http://www.infoarena.ro/problema/bfs
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int n, m, s, G[20000][20000], prim, ultim, c[1000000], v[1000000], o;

void Read()
{
    int b, y;
    f >> n >> m >> s;
    for(int i = 1; i <= m; i++)
        f >> b >> y, G[b][y] = 1;
}

void bfs(int x[])
{
    int varf;
    o = 0; x[s] = 0;
    bool p = 1;
    while(prim <= ultim)
    {
        if(p)
            o++;
        p = 0;
        varf = c[prim];
        for(int k = 1; k <= n; k++)
            if(G[varf][k] == 1 && v[k] == 0)
                ultim++, c[ultim] = k, v[k] = 1, x[k] = o, p = 1;
        prim++;
    }
}

int main()
{
    int x[10000];
    Read();
    for(int i = 1; i <= n; i++)
        x[i] = -1;
    prim = ultim = 1;
    c[prim] = s;
    v[s] = 1;
    bfs(x);
    for(short i = 1; i <= n; i++)
            g << x[i] << " ";
    return 0;
}