#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
void construire(int m, vector<vector<int>>& ls) {
	for (int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		ls[x].push_back(y);
		
	}
}

void afisare(vector<vector<int>>ls) {
	for (int i = 1; i < ls.size(); i++)
	{
		cout << i<<": ";
		for (int j = 0; j < ls[i].size(); j++)
		{
			cout << ls[i][j] << " ";
		}
		cout << "\n";
	}
}
int v[100000];
void parcurgere(vector<vector<int>>ls, int s,int n) {
	v[s] = 1;
	int st = 0, dr = 0,k=0;
	int x[100000];
	x[0] = s;
	
	while (st <= dr) {	
		int y = x[st];
		int drv = dr;
		for (int i = 1; i < ls.size(); i++)
		{
			if (v[i] == 0 && find(ls[y].begin(), ls[y].end(), i)!=ls[y].end()) {
				v[i] = 1+k;
				x[++dr] = i;
			}
		}
		if (drv != dr)
			k++;
		st++;
	}
	
	for (int i = 1; i < ls.size(); i++)
	{
		if (v[i] == 0)
			v[i] = -1;
	}
	v[s] = 0;

}

int main() {
	
	int n, m, s;
	in >> n >> m >> s;
	vector<vector<int>>ls(n+1);

	construire(m,ls);
	
	
	parcurgere(ls, s, n);
	for (int i = 1; i < ls.size(); i++)
	{
		out << v[i] << " ";
	}
	return 0;
}