#include <fstream>
#include <list>
#define Nmax 100001
using namespace std;

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

int n, m, coada[ Nmax ], ans[ Nmax ], j, in, sf;
list < int > graph[ Nmax ];

int main()
{
    int x, y;

    f >> n >> m >> j;

    for ( int i = 1; i <= n; ++ i )
        ans[ i ] = -1;

    for ( int i = 1; i <= m; ++ i )
    {
        f >> x >> y;
        graph[ x ].push_back( y );
    }

    ans[ j ] = 0;
    coada[ 1 ] = j;
    in = sf = 1;

    while ( in <= sf )
    {
        for ( list < int > :: iterator it = graph[ coada[ in ] ].begin(); it != graph[ coada[ in ] ].end(); ++ it )
        {
            if ( ans[ *it ] == -1 )
            {
                ans[ *it ] = ans[ coada[ in ] ] + 1;
                coada[ ++sf ] = *it;
            }
        }
        in ++;
    }

    for ( int i = 1; i <= n; ++ i )
        g << ans[ i ] << " ";

    return 0;
}