#include<fstream>
#define dmax 100002
#define amax 1000002
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
struct arce
{	int s;
	int f;
}	drum[amax];	
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(i=1;i<=m;i++)
		{	if(drum[i].s==c[p1].nod)
				if(v[drum[i].f]==0)
				{	p2++;
					c[p2].nod=drum[i].f;
					v[drum[i].f]=1;
					if((c[p1].pas+1>minim[drum[i].f])||(minim[drum[i].f]==-1))
					{	minim[drum[i].f]=c[p1].pas+1;
						c[p2].pas=c[p1].pas+1;
					}	
				}
		}
		p1++;	
	}
}	
int main()
{	int i;
	in>>n>>m>>s;
	for(i=1;i<=m;i++)
		in>>drum[i].s>>drum[i].f;
	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;
}