#include<stdio.h>
#include<vector>
#define N 100001
#include<deque>

using namespace std;

int n,m,s;
vector<int> graph[N];
int ans[N];
deque<pair<int,int>> q;



int main(){
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
    }
    for(int i=0;i<=n;++i)ans[i]=-1;
    ans[s]=0;
    q.push_back(pair<int,int>(s,0));
    while(q.size()>0){
        pair<int,int> t = q.front();
        q.pop_front();
        for(int i=0;i<graph[t.first].size();++i){
            int node = graph[t.first][i];
            if(ans[node]>-1)continue;
            ans[node]=t.second+1;
            q.push_back(pair<int,int>(node,ans[node]));
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
}