#include <fstream>
#include <vector>
#define NMAX 100001

using namespace std;

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

struct nod
{
    int pasi;
    int nod;
}act, qu[NMAX];

vector < int > graf[NMAX];

int n, m, s, x, y, inc, sf, drum[NMAX], i;

void citire()
{
    f >> n >> m >> s;


    for( i = 1; i <= m; i++ )
    {
        f >> x >> y;

        graf[x].push_back(y);
    }
}

void initializare()
{
    for( i = 1; i <= n; i++)
        drum[i] = -1;

    inc = sf = 1;

    qu[inc] = {0, s};
    drum[s] = 0;
}

void bfs()
{
    initializare();

    while( inc <= sf )
    {
        act = qu[inc++];

        int sze = graf[act.nod].size() - 1;

        for( i = 0; i <= sze; i++ )
        {
            if( drum[ graf[ act.nod ][ i ] ] < 0 )
            {
                drum[ graf[ act.nod ][ i ] ] = act.pasi + 1;
                qu[++sf] = { act.pasi + 1, graf[ act.nod ][ i ] };
            }
        }
    }
}

void afisare()
{
    for( i = 1; i <= n; i++ )
        g << drum[ i ] << " ";
}

int main()
{
    citire();
    bfs();
    afisare();
}