#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf{
private:
    int Nr_Noduri, Nr_Muchii;
    vector < vector<int> > matrice_adiacenta;
    
public:
    Graf(int N, int M, vector< vector<int> > & matrice); // constructor
    vector < vector<int> > getMatriceAdiacenta()
    {
        return matrice_adiacenta;
    }

    void Citire_Graf_Orientat();
    void BFS(int nod_Start);
};

// constructor
Graf :: Graf(int N, int M, vector < vector<int> > & matrice)
{
    Nr_Noduri = N;
    Nr_Muchii = M;
    matrice_adiacenta = matrice;
}

void Graf :: Citire_Graf_Orientat()
{
    for ( int i = 1; i <= Nr_Muchii; i++ )
    {
        int x, y;
        fin >> x >> y;
        matrice_adiacenta[x].push_back(y);
    }
}

void Graf :: BFS(int nod_Start)
{
    queue <int> Q;
    int x, y;
    vector <int> cost (Nr_Noduri+1, -1);

    // inserez nodul de start in coada vida, iar acesta va avea costul 0
    cost[nod_Start] = 0;
    Q.push(nod_Start);

    while ( !Q.empty() )
    {
        // la fiecare pas luam nodul din inceputul cozii, dupa care il eliminam
        x = Q.front();
        Q.pop();

        for ( int i = 1; i < matrice_adiacenta[x].size(); i++ )
            if ( cost[matrice_adiacenta[x][i]] == -1 )
            {
                // costul unui nod nou adaugat va fi costul nodului care l-a adaugat + 1.
                cost[matrice_adiacenta[x][i]] = cost[x] + 1;
                Q.push(matrice_adiacenta[x][i]);
            }
    }

    // afisare costuri
    for ( int i = 1; i <= Nr_Noduri; i++ )
        fout << cost[i] << " "; 
}

int main()
{
    int N, M, S;
    fin >> N >> M >> S;
    
    vector < vector<int> > matrice;
    vector <int> aux(1,-1);
    matrice.resize(N+1, aux);

    Graf G(N, M, matrice);
    G.Citire_Graf_Orientat();

    G.BFS(S);

    return 0;
}