using namespace std;

#include <fstream>
#include <vector>

ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector <int> G[100005];
int N, M, S, D[100005], Use[100005], C[100005];

void BFS()
{
	C[1]=S; 
	int k=1;
	Use[S]=1;
	for(int i=1; i<=k; i++)
	{
		int Nod=C[i];
		for(unsigned int j=0; j<G[Nod].size(); j++)
		{
			int Vecin=G[Nod][j];
			if(!Use[Vecin])
			{
				C[++k]=Vecin;
				D[Vecin]=D[Nod]+1;
				Use[Vecin]=1;
			}
		}
	}
	
}
int main()
{
		fin>>N>>M>>S;
		for(int i=1; i<=M; i++)
		{
			int x, y;
			fin>>x>>y;
			G[x].push_back(y);
	
		}
		for(int i=1; i<=N; i++)
			D[i]=-1;
		D[S]=0;
		BFS();
		for(int i=1; i<=N; i++)
			fout<<D[i]<<" ";
		
		return 0;
}