#include<fstream>
#include<vector>
#define dmax 100002
#define amax 1000002
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
vector<int>ad[dmax];
vector<int>::iterator it;
struct queue
{	int nod;
	int pas;
}	c[dmax];	
int n,m,s,minim[dmax];
bool v[dmax];
void bf()
{	int p1=1,p2=1,i;
	c[1].nod=s;
	c[1].pas=0;
	v[s]=1;
	minim[s]=0;
	while(p1<=p2)
	{	for(it=ad[c[p1].nod].begin();it<ad[c[p1].nod].end();it++)	
		{	
			if(v[*it]==0)
			{	p2++;
				c[p2].nod=*it;
				v[*it]=1;
				if((minim[*it]>c[p1].pas+1)||(minim[*it]==-1))
				{	minim[*it]=c[p1].pas+1;
					c[p2].pas=c[p1].pas+1;
				}
			}
		}
		p1++;
	}	
}	
int main()
{	int i,x,y;
	in>>n>>m>>s;
	for(i=1;i<=m;i++)
	{	in>>x>>y;
		ad[x].push_back(y);
	}	
	in.close();
	for(i=1;i<=n;i++)
		minim[i]=-1;
	bf();
	for(i=1;i<=n;i++)
		out<<minim[i]<<" ";
	out.close();
	return 0;
}