#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector<vector <int> > graf;
vector<int> vis;
int m,n,s;

void bfs(int vert)
{
	if(vert<0|| vert>n-1)
		return;
	int element,i=0;
	queue<int> q;
	q.push(vert);
	vis[vert]=1;
	while(!q.empty())
	{
		element=q.front();
		for(i=0;i<graf[element].size();i++)
		{
			if(!vis[graf[element][i]])
			{
				q.push(graf[element][i]);
				vis[graf[element][i]]=vis[element]+1;
			}
		}
		q.pop();
	}
}

int main()
{
    ifstream in("bfs.in");
	in>>n>>m>>s;
	graf.resize(n);
	vis.resize(n,0);
	int x,y;
	for(int i=0;i<m;i++)
	{
		in>>x>>y;
		x--;
		y--;
		graf[x].push_back(y);
	}
	bfs(s-1);
	ofstream out("bfs.out");
	for(int i=0;i<vis.size() && i<n;i++)
	{
		out<<vis[i]-1<<" ";
	}
	return 0;
}