#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
const int N=1e5+5;
vector<pair<int,int>> g[N];
int dist[N];
signed main()
{
    ifstream cin("bfs.in");ofstream cout("bfs.out");
    int n,m,root;
    cin>>n>>m>>root;
    for(int _=1;_<=m;++_)
    {
        int u,v,w=1;cin>>u>>v;
        g[u].pb({v,w});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,root});
    for(int i=1;i<=n;++i) dist[i]=1e9;
    dist[root]=0;
    while(!pq.empty())
    {
        int u=pq.top().second,w=pq.top().first;
        pq.pop();
        if(w!=dist[u]) continue;
        for(auto v:g[u])
        {
            if(w+v.second>=dist[v.first]) continue;
            dist[v.first]=w+v.second;
            pq.push({dist[v.first],v.first});
        }
    }
    for(int i=1;i<=n;++i) {if(dist[i]==1e9) dist[i]=-1;cout<<dist[i]<<" ";}
}