#include<fstream>
#include<vector>
#include<deque>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int NMAX=100005;
int n,m,s;
vector<int>v[NMAX],drum(NMAX,-1);
void adiacenta(){
    int i,j;
    fin>>n>>m>>s;
    while(m--){
        fin>>i>>j;
        v[i].push_back(j);
    }
}
void BFS(){
    int nod=s,i;
    deque<int>d;
    d.push_back(nod);
    drum[nod]=0;
    while(!d.empty()){
        nod=d.front();
        d.pop_front();
        for(i=0;i<v[nod].size();++i)
            if(drum[v[nod][i]]==-1){
                d.push_back(v[nod][i]);
                drum[v[nod][i]]=drum[nod]+1;
            }
    }
}
void afisare(){
    int i;
    for(i=1;i<=n;++i)
        fout<<drum[i]<<' ';
}
int main(){
    adiacenta();
    BFS();
    afisare();
}