#include<fstream>
#include<vector>
#define N 100006 
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n,m,s;
int viz[N];
int C[N];
int nr[N];
vector <int> a[N];
int main()
{	int i,x,y;
	f>>n>>m>>s;
	for(i=1;i<=m;i++) 
	{	f>>x>>y;
		//a[x][y]=1;
		a[x].push_back(y);
	}
	for(i=1;i<=n;i++) nr[i]=-1;
	viz[s]=1;
	C[1]=s;
	nr[s]=0;
	int p=1,u=1;
	while(p<=u)
	{	int v=C[p++];
		vector <int> :: iterator it=a[v].begin(), sf=a[v].end();
		for(;it!=sf;it++) 
			if(viz[*it]==0) {C[++u]=i; nr[*it]=nr[v]+1; viz[*it]=1;}
	}
	for(i=1;i<=n;i++) g<<nr[i]<<" ";
	g<<'\n'; g.close(); return 0;
}