#include<bits/stdc++.h>

using namespace std;

vector <int> list[100001];
queue <int> q;
int n, m, s, x, y;
bool visit[100001];
int a[100010];


void bfs(int node)
{
	q.push(s);
	visit[node] = 1;
	a[node] = 1;

	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int i = 0; i < list[t].size(); i++)
		{
		    if (!visit[list[t][i]])
			{
			    q.push(list[t][i]);
				visit[list[t][i]] = 1;
				a[list[t][i]] = a[t] + 1;
			}
		}
	}
}

int main ()
{
	ifstream cin("bfs.in");
	ofstream cout("bfs.out");

	cin >> n >> m >> s;

	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		list[x].push_back(y);
	}

	bfs(s);

	for (int i = 1; i <= n; i++)
	    cout << a[i]-1 <<" ";
    return 0;
}
/*Depresia clinică este o stare mentală de tristețe/amărăciune care persistă pe perioade îndelungate.

Simptome care durează mai mult de două săptămâni și de o severitate care începe să împiedice desfășurarea normală a activităților zilnice deja semnifică depresie clinică.

Se presupune că doar o mică parte din cei care suferă de depresie ajung să conștientizeze această afecțiune și să se supună tratamentului corespunzător. Motivele sunt frica de stigmatizare socială, orgoliul personal și ignoranța.

Spre deosebire de credința populară, chiar și cazurile de depresie severă pot fi tratate medical și vindecate.

Se estimează că în anul 2020 depresia va deveni a doua cauză de dizabilitate la nivel mondial, după afecțiunile cardiovasculare. În prezent, boala afectează aproximativ 121 milioane de oameni pe glob. În România, a fost depistată o creștere semnificativă a episodului depresiv major odată cu vârsta, de la 2,1% – 2,6% (18-49 ani) la 4,4% – 5,2 % (peste 50 de ani) cu un ritm de creștere de 1,2 puncte procentuale pentru fiecare grupă de vârstă (50-64 ani și peste 65 de ani).[1]*/