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

using namespace std;

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

int n, m, s;

struct node
{
    int nrVecini;
    vector<int> vecini;
    int nrArce;
}v[100001];

void citire()
{
    fin >> n >> m >> s;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        v[a].vecini.push_back(b);
    }
}

void verificare()
{
    for(int i = 1; i <= n; i++)
    {
        fout << i << ": ";
        for(auto &j : v[i].vecini)
            fout << j << ' ';
        fout << '\n';
    }
}

void initializare()
{
    for(int i = 1; i <= n; i++)
    {
        v[i].nrArce = -1;
        v[i].nrVecini = v[i].vecini.size();
    }
}

void rezolvare()
{
    queue<int> coada;
    v[s].nrArce = 0;
    coada.push(s);
    while(!coada.empty())
    {
        int top = coada.front();
        coada.pop();
        for(int i = 0; i < v[top].nrVecini; i++)
            if( v[ v[top].vecini[i] ].nrArce == -1 )
            {
                coada.push(v[top].vecini[i]);
                v[ v[top].vecini[i] ].nrArce = v[top].nrArce + 1;
            }
    }
}

void afisare()
{
    for(int i = 1; i <= n; i++)
        fout << v[i].nrArce << ' ';
}

int main()
{
    citire();
    //verificare();
    initializare();
    rezolvare();
    afisare();
    return 0;
}