#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int n, m, s;
vector< vector<int> >a;
bool v[100002];
queue<int>Q;
vector<int> t, d;

void Read();
void BFS(int nod);
void Write();

int main()
{
	Read();
	BFS(s);
	Write();
	return 0;
}

void Read()
{
	ifstream fin("bfs.in");
	fin >> n >> m >> s;
	a.resize(n+1);
	t.resize(n+1);
	d.resize(n+1);
	
	int x, y;
	for(int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		a[x].push_back(y);
	}
	for(int i = 1; i <= n; ++i)
		d[i] = -1;
	fin.close();
}
	
void BFS(int s)
{
	int j;
	Q.push(s);
	v[s] = 1;
	t[s] = 0;
	d[s] = 0;
	
	while( !Q.empty() )
	{
		j = Q.front();
		Q.pop();
		for(int i = 0; i < (int)a[j].size(); ++i)
		{
			int k = a[j][i];
			if( !v[k] )
			{
				Q.push(k);
				v[k] = 1;
				t[k] = j;
				d[k] = d[j] + 1;
			}
		}
	}
}

void Write()
{
	ofstream fout("bfs.out");
	for(int i = 1; i <= n; ++i)
		fout << d[i] << " ";
	fout.close();
}