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

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_muchii, start;
    vector <int> lista_adiacenta[10001];

public:

    void citire_elemente();
    void bfs();
};

/// functia de citire
void Graf :: citire_elemente()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri >> numar_muchii >> start;

    for(int i = 1; i <= numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
    }
}

/// algoritmul bfs
void Graf :: bfs()
{
    int nod_curent;
    queue <int> coada;
    int vizitare[numar_noduri] = {0};

    // adaugam in coada nodul de start
    coada.push(start);
    vizitare[start] = 1;

    int cost_nod[10001] = {};
    cost_nod[start] = 0;

    while(coada.size() > 0)
    {
        nod_curent = coada.front();

        for(int i = 0; i < lista_adiacenta[nod_curent].size(); i++)
            if(!vizitare[lista_adiacenta[nod_curent][i]])
        {
            coada.push(lista_adiacenta[nod_curent][i]);
            cost_nod[lista_adiacenta[nod_curent][i]] = cost_nod[nod_curent] + 1;
            vizitare[lista_adiacenta[nod_curent][i]] = 1;
        }
        coada.pop();
    }

    for(int i = 1; i <= numar_noduri; i++)
        if(vizitare[i])
            fout << cost_nod[i] << " ";
        else
            fout << -1 << " ";

}

int main()
{
    Graf x;
    x.citire_elemente();
    x.bfs();

    fin.close();
    fout.close();

    return 0;
}