#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int dist[1000005];                //un vector de muchii vizitate
vector<int> listaMuchii[1000005]; //vector pentru lista de muchii
queue<int> coadabfs;
void bfs(int nod)
{
    int nod_curent;
    dist[nod] = 0;      //distanta din nodul din care plecam este bineinteles 0
    coadabfs.push(nod); //adaugam nodul dat in coada pentru parcurgere
    //cat timp coada de parcurgere nu ramane goala
    while (!coadabfs.empty())
    {
        //luam primul nod din coada in nod_curent
        nod_curent = coadabfs.front();
        coadabfs.pop();
        //parcurgem lista de adiacenta a nodului curent
        for (int i = 0; i < listaMuchii[nod_curent].size(); i++)
        {
            if (dist[listaMuchii[nod_curent][i]] == -1) //daca nu am mai ajuns pana acum in acest nod
            {
                //marim distanta drumului cu 1 + distanta parcursa pana acum
                dist[listaMuchii[nod_curent][i]] = dist[nod_curent] + 1;

                //adaugam noul nod gasit in coada
                coadabfs.push(listaMuchii[nod_curent][i]);
            }
        }
    }
}

int main()
{
    int x, y, i, noduri, muchii, nod, nrConexe = 0;
    fin >> noduri >> muchii >> nod;
    //facem lista de muchii/adiacenta ale grafului
    for (i = 0; i < muchii; i++)
    {
        fin >> x >> y;
        listaMuchii[x].push_back(y);
    }
    for (i = 1; i <= noduri; i++)
    {
        dist[i] = -1; // daca nu se poate ajunge la un nod, distanta default e -1
    }
    bfs(nod);
    for (i = 1; i <= noduri; i++)
    {
        fout << dist[i] << " ";
    }

    return 0;
}