#include <fstream>
using namespace std;
ofstream fout("bfs.out");
ifstream fin("bfs.in");
int n,m,start[100002],viz[100002],d[100002],s,x,y,coada[100002],pr,ul,nr;
struct {
    int vecin,leg;
} L[1000002];



int main() {
    fin >> n >> m >> s;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        L[i].vecin=y;
        L[i].leg=start[x];
        start[x]=i;
    }
    for (int i = 1; i <= n; ++i) {
        d[i]=-1;
    }
    d[s]=0;
    coada[1]=s;
    viz[s]=1;
    pr=1;
    ul=1;
    nr=1;
    while(nr>0){
        x=coada[pr];
        for (int i = start[x]; i !=0 ; i=L[i].leg) {
            y=L[i].vecin;
            if(viz[y]==0){
                viz[y]=1;
                ul++;
                coada[ul]=y;
                nr++;
                d[y]=d[x]+1;
            }
        }
        pr++;
        nr--;
    }
    for (int i =1; i <=n ; ++i) {
        fout << d[i] << " ";
    }
    return 0;
}