#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bfs.in"); // conex si m=n-1
ofstream fout ("bfs.out");

vector<int> a[100001];//in loc de matrice 
int n,m,start,x,y;
int vizite[100001],distanta[100001];
queue<int> orase;// va memora orasele prin care trece k 
void BFS(int start){
    vizite[start]=1;
    distanta[start]=0;
    orase.push(start);
    while(!orase.empty()){
        int city=orase.front();
        for(auto vecin:a[city]){
            if (vizite[vecin]==0){
                vizite[vecin]=1;
                orase.push(vecin);
                distanta[vecin]=distanta[city]+1;//adaug 1 la fiecare adiacenta 
            }
        }
       orase.pop();//sterge orasul din captul cozii ca sa putem lua urmatorul oras 
    }
}
int main()
{
    
    fin>>n>>m>>start;
    while(fin>>x>>y){
        a[x].push_back(y);
    }
    for(int i=1;i<=n;++i){
        sort(a[i].begin(),a[i].end());
    }
    for(int i=1;i<=n;++i){
        distanta[i]=-1;
    }
    BFS(start);//incepem de la punctul de start
    for(int i=1;i<=n;++i){
        fout<<distanta[i]<<" ";
    }
    return 0;
}