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

using namespace std;

vector <int> graf[1000000 + 5];
vector <int> viz;
vector <int> coada;
vector <int> cost;

bool coada_goala()
{
    int l = coada.size();
    for(int i = 0; i < l; ++i)
    {
        if(viz[coada[i]] == 0 && coada[i] != -1)
            return false;
    }
    return true;
}

void bfs(int &poz_nod)
{
    int nod = coada[poz_nod];
    viz[nod] = 1;
    int l = graf[nod].size();
    int j = poz_nod;
    for(int i = 0; i < l; ++i)
    {
        j++;
        int vecin = graf[nod][i];
        if(viz[vecin] == 0)
        {
            coada[j] = vecin;
            cost[vecin] = cost[nod] + 1;
        }
    }
}

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

    if(f == NULL)
    {
        cout << "Eroare deschidere fisier";
        return -1;
    }
    int n, m, s;
    f >> n >> m >> s;
    //citesc datele
    for(int i = 0; i < m; ++i)
    {
        int a, b;
        f >> a >> b;
        graf[a].push_back(b);
    }

    //setare dimensiuni vectori
    viz.resize(n+1);
    coada.resize(2*(n+1));
    cost.resize(n+2);
    for(int i = 1; i <= n; ++i)
    {
        cost[i] = -1;
    }
    int lim = coada.size();
    for(int i = 0; i < lim; ++i)
        coada[i] = -1;

    coada[0] = s;
    cost[s] = 0;
    int poz_nod = 0;

    while(coada_goala() == false && poz_nod < n)
    {
        bfs(poz_nod);
        poz_nod++;
    }

    for(int i = 1; i <= n; ++i)
        g << cost[i] << ' ';

    f.close();
    g.close();
    return 0;
}