#include<fstream>
#include<queue>
#define MAXN 100010
#define inf 100000000

using namespace std;

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

struct graf
{
	int nod;
	graf *next;
};

graf *a[MAXN];

int n,s,m,d[MAXN];


void read()
{
	in>>n>>m>>s;
	int i,x,y;
	for(i=1;i<=m;i++)
	{
		in>>x>>y;
		graf *q=new graf;
		q->nod=y;
		q->next=a[x];
		a[x]=q;
	}
}

void bfs()
{
	bool inqueue[MAXN];
	for(int i=1;i<=n;i++)
	{
		d[i]=inf;
		inqueue[i]=false;
	}
	queue<int> q;
	q.push(s);	
	d[s]=0;
	inqueue[s]=true;
	while(!q.empty())
	{
		int min=q.front();
		q.pop();
		graf *g=a[min];
		while(g)
		{
			if(inqueue[g->nod]==false)
			{
				inqueue[g->nod]=true;
				d[g->nod]=d[min]+1;
				q.push(g->nod);
			}
			g=g->next;
		}		
	}
}

int main()
{
	read();
	bfs();
	for(int i=1;i<=n;i++)
	{
		if(d[i]==inf)
			out<<"-1"<<" ";
		else
		out<<d[i]<<" ";
	}
	return 0;
}