#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n,m,s,x,y,viz[100001];
//q e "randul" nodurilor.


//s = nodul de start
//viz verifica numarul de laturi dintre nodul s si nodul curent reprezentat de iterator
queue <int> q;
vector <int> v[100001];
void bfs(){

    viz[s]=0;
    q.push(s);
    while(!q.empty()){
    int x=q.front();
    q.pop();
    for(vector<int> :: iterator i=v[x].begin(); i!=v[x].end();i++)
    {
        if(viz[*i] == -1)
        {
            viz[*i]=viz[x] + 1;
            q.push(*i);
        }
    }
    }
}
int main(){
fin>>n>>m>>s;
while(m){
    fin>>x>>y;
    v[x].push_back(y);
    m--;
}

for(int i=1;i<=n;i++)
viz[i] = -1;

bfs();

for(int i = 1; i <= n; ++ i)
        fout << viz[i] << " ";
    
}


/*
INGREDIENTE pentru un chec pufos:

5 oua
200 grame de faina
200 grame zahar
1 plic de praf de copt
1 plic de zahar vanilat
2 linguri de cacao
4 linguri de ulei
1 praf de sare
100 ml lapte
PREPARARE si TRUCURI DE LA BUNICA pentru un chec pufos

Separa albusurile de galbenusuri. Galbenusurile le vei bate cu zahar. E mai bine sa folosesti zahar pudra, caci se topeste imediat.

Albusurile le vei bate spuma. Pune in ele putina zeama de lamaie (sau chiar un strop de otet, spune bunica) sau un praf de sare, ca sa se intareasca si sa devina o spuma perfecta.

Amesteca galbenusurile cu uleiul si faina. Bunica spuna sa pui faina putin cate putin, in timp ce amesteci, ca sa nu ai cocoloase. Asa sigur vei avea un chec pufos. Amesteca si laptele la temperatura camerei.

Amesteca si albusurile batute spuma si amesteca usor cu o lingura – daca ai amestecat pana acum cu mixerul, uita de el cand incorporezi albusurile.

Imparte aluatul de chec in doua: intr-o jumatate de compozitie pui vanilie, iar in alta pui cacao. Pune in tava o parte din compozitie, apoi toarn-o si pe a doua si cu o furculita sau un betisor pentru frigarui, marmoreaza checul.

Checul pufos se poate prepara si doar cu cacao (in acest caz pui 3-4 linguri de cacao) sau doar cu vanilie (cu 2-3 pliculete de zahar vanilat). Poti sa pui in acest chec pufos nuci, ciocolata, stafide si alte fructe uscate, poti sa il servesti pudrat cu zahar sau cu nuca de cocos.

Oricum ai pregati checul pufos, nu uita de cel mai important ingredient, secretul bunicii: dragostea!

Pofta buna!

VEZI SI: Reteta de chec foarte sănătos din fructe uscate. Arata superb și este incredibil de delicios!


 */