#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

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

int nrmuchii, nrnoduri, i, j, start, fata, spate;


int main()
{
    fin >> nrnoduri >> nrmuchii >> start;
    vector <int> vecini[nrnoduri];
    vector <int> rez;
    vector <int> cost;
    cost.assign(nrnoduri, -1);
    int coada[nrnoduri+1];
    bool viz[nrnoduri];
    memset(viz, 0, sizeof(viz));
    memset(coada, 0, sizeof(coada));
    while (fin >> i >> j)
        vecini[i-1].push_back(j);
    for (i = 0; i < nrnoduri; i++)
    {
        sort(vecini[i].begin(), vecini[i].end());
        if (vecini[i].size())
            for (auto j = vecini[i].end()-1; j > vecini[i].begin(); j--)
                if (*j == *(j-1))
                    vecini[i].erase(j);
    }
    viz[start-1] = 1;
    coada[0] = start;
    cost[start-1] = 0;
    while (coada[spate])
    {
        for (auto i : vecini[coada[spate]-1])
        {
            if (viz[i-1] == 0)
            {
                coada[++fata] = i;
                cost[i-1] = cost[coada[spate]-1]+1;
                viz[i-1] = 1;
            }
        }
        spate++;
    }
    for (i = 0; i < nrnoduri; i++)
        fout << cost[i] << ' ';

    return 0;
}