#include <bits/stdc++.h>

using namespace std;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

vector<int> a[100001];
queue<int> orase;
int n,m,start,x,y,i,curent,vizitate[100001],dist[100001];

int main()
{
    fin>>n>>m>>start;
    memset(dist,-1,sizeof(dist));           //umplem dist[] cu -1, pt aia de nu au vecini
    for(i=0;i<m;i++){
        fin>>x>>y;
        a[x].push_back(y);
    }
    for(auto element: a)sort(element.begin(),element.end());
    orase.push(start);
    vizitate[start]=1;
    dist[start]=0;                          //ca sa nu fie totu cu 1 in minus
    while(!orase.empty()){
        curent=orase.front();
        for(auto element: a[curent]){
            if(vizitate[element]==0){
                vizitate[element]=1;
                orase.push(element);
                dist[element]=dist[curent]+1;   //formula cheie
            }
        }
        orase.pop();
    }
    for(i=1;i<=n;i++)fout<<dist[i]<<" ";
    return 0;
}

//Primii is vecini direct, urmatorii sunt vecini ai vecinilor, deci distanta lor pana la s este distanta curentului pana la s + 1, si tot asa...