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

using namespace std;

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

const int NMAX = 100005;
const int INF = 2e7;

vector<int>G[NMAX];
int dist[NMAX];
bool viz[NMAX];
int n, m, s;


void read()
{
	fin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[s] = 0;
	while (m--)
	{
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
	}
}

void bfs(int start)
{
	queue<int>q;
	q.push(start);
	while (!q.empty())
	{
		int u = q.front();
		viz[u] = true;
		q.pop();

		for (int v : G[u])
		{
			if (dist[u] + 1 < dist[v] && !viz[v])
			{
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
}

void solve()
{
	bfs(s);
	for (int i = 1; i <= n; i++)
		fout << (dist[i] == INF ? -1 : dist[i]) << ' ';
}

int main()
{
	read();
	solve();
	return 0;
}