#include<fstream>
#define Max 1000001

using namespace std;

int t[2][Max],start[Max],m,n,pus[Max],s,cost[Max],b[Max];
void read()
{
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");

	int i,x,y,k=0;
	
	fin>>n>>m>>s;

	for(i = 1; i <= m; i++)
	{
		fin>>x>>y;
		k++;
		t[0][k] = y;
		t[1][k] = start[x];
		start[x] = k;
	}
fin.close();
}
void bf()
{
	int st,dr,nod;
	st = 1;
	dr = 1;
	while(st <= dr)
	{
		nod = start[b[st]];
		while(nod != 0)
		{
			if(!pus[t[0][nod]])
			{
				dr++;
				b[dr] = t[0][nod];
				pus[t[0][nod]] = 1;
				cost[t[0][nod]] = cost[b[st]]+1;
			}
				nod = t[1][nod];
		}
		st++;
	}
}
				
int main()
{
	ofstream fout("bfs.out");
	int i;
	read();
	b[1] = s;
	pus[s] = 1;
	bf();
for(i = 1; i <= n; i++)
	if(i != s && cost[i] == 0)
	fout<<-1<<" ";
	else
	fout<<cost[i]<<" ";

fout.close();

return 0;

}