#include <iostream>
#include <vector>
#include <fstream>
#define maxn 100005

using namespace std;

int N,M,Start,x,y,L;
vector <int> a[maxn];
int g[maxn],s[maxn],cost[maxn];

int main()
{
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    in >> N >> M >> Start;
    for(int i=1;i<=M;i++){
        in >> x >> y;
        a[x].push_back(y);
    }
    for(int i=1;i<=N;i++){
        g[i]=a[i].size();
    }
    for(int i=1;i<=N;i++) cost[i]=-1;
    L=1;
    cost[Start]=0;
    s[L]=Start;
    for(int i=1;i<=L;i++){
        for(int j=0;j<g[s[i]];j++){
            if(cost[a[s[i]][j]]==-1){
                s[++L]=a[s[i]][j];
                cost[s[L]]=cost[s[i]]+1;
            }
        }
    }
    for(int i=1;i<=N;i++){
        out << cost[i] << ' ';
    }
    return 0;
}