#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 = 2e9;

struct edge {
	int y, cost;
	bool operator<(const edge& other) const {
		return cost > other.cost;
	}
};

priority_queue<edge>pq;
vector<edge>G[NMAX];

int distMin[NMAX];
bool viz[NMAX];

int m, n;

void dijkstra(int nod)
{
	for (int i = 1; i <= n; i++)
		distMin[i] = INF;
	
	pq.push(edge({ nod,0 }));

	while (!pq.empty())
	{
		edge u = pq.top();
		pq.pop();

		if (distMin[u.y] != INF) continue;

		distMin[u.y] = u.cost;

		for (edge v : G[u.y])
			pq.push(edge({v.y, v.cost+u.cost}));
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);
	int k;
	fin >> n >> m >> k;
	while (m--)
	{
		int a, b, c;
		fin >> a >> b;
		G[a].push_back(edge({ b,1 }));
	}
	dijkstra(k);
	for (int i = 1; i <= n; i++)
		fout << ((distMin[i] == INF) ? -1 : distMin[i]) << ' ';
	fout << '\n';
	return 0;
}