#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=100001;
using namespace std;

int t=1,n,m,s;
vector<vector<int>> A(maxn,vector<int>());
int depth[maxn],chk[maxn];

int main(){
	ifstream cin("bfs.in");
	ofstream cout("bfs.out");
	cin>>n>>m>>s;
	s--;
	for(int i=0;i<m;i++){
		int c1,c2;
		cin>>c1>>c2;
		c1--;
		c2--;
		A[c1].push_back(c2);
	}
	for(int i=0;i<n;i++)depth[i]=1e9;
	depth[s]=0;
	queue<int> Q;
	Q.push(s);
	chk[s]=1;
	while(Q.size()){
		int i=Q.front();
		Q.pop();
		chk[i]=1;
		for(int j=0;j<A[i].size();j++){
			if(chk[A[i][j]]==0){
				depth[A[i][j]]=min(depth[i]+1,depth[A[i][j]]);
				Q.push(A[i][j]);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(depth[i]==1e9)cout<<-1<<" ";
		else cout<<depth[i]<<" ";
	}
}