//daca se uita cineva pe sursa asta ii sugerez sa citeasca acest link
//dupa care sa fie atent la alte explicatii din aceasta sursa
//http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/
using namespace std;
#include<fstream>
#include<vector>
#include<queue>

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

vector<vector<int> > graf;
queue<int> stiva;
int cost[100005];

int n,m,s;

void setup(){
    for(int i=1;i<=n;i++)
        cost[i]=-1;//presupunem ca nu putem ajunge la nici un nod,cele pe care le modifacam vor avea costul de la s la ele
}
void trecere(int k){
    stiva.push(k);
    cost[k]=0;

    while(!stiva.empty()){
        int x = stiva.front();
        stiva.pop();

        for(int i=0;i<graf[x].size();i++){
            if(cost[graf[x][i]]==-1){//verficam daca nodul nu a mai fost vizitat,nodurile care nu pot fi vizitate raman -1
                stiva.push(graf[x][i]);//se adauga in stiva intreg nivelul urmator(ex:avem nivelul form din nodurile 2 si 3 si pe rand sunt adaugati vecini lor care nu au fost adaugati deja)
                cost[graf[x][i]]=cost[x]+1;//nodurile din niv memorat primesc costul nodului din care "se trag" plus 1(ex: daca trebuie sa aflam costurile de la 3 la toate nodurile si avem de la 3 la 2 cost unu atunci toate nodurile care sunt vecini daor cu 2 au costul lui plus unu
            }
        }
    }
}


int main(){
    in>>n>>m>>s;

    graf.resize(n+1);

    for(int i=1;i<=m;i++){
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
        }
    setup();
    trecere(s);
    for(int i=1;i<=n;i++)
        out<<cost[i]<<" ";
    out.close();
    return 0;
}