#include <fstream>
#include <iostream>

using namespace std;

ifstream fi("bfs.in");
ofstream fo("bfs.out");
int n, m, s, a[2000][2000], l, c, i, nc, coada[2000], p, u, d[2000];

int main() {
	fi >> n >> m >> s;
	for (i = 1; i <= m; i++) {
		fi >> l >> c;
		a[l][c] = 1;
	}
	p = 1; u = 1; // pozitia primului, respectiv ultimului element din coada
	for (i = 1; i <= n; i++)
    d[i] = -1;
	coada[1] = s; d[s] = 0;
	while (p <= u) {      // cat timp exista elemente in coada
		nc = coada[p];      // Extragem nodul curent.
		for(i = 1; i <= n; i++) // Pentru fiecare nod
			if (a[nc][i] && d[i] == -1){ // Este vecin nevizitat al nodului curent?
        u++; coada[u] = i; d[i] = d[nc]+1; // Il punem in coada.
			}
		p++; // Scoatem din coada nodul curent.
	}
	for (i = 1; i <= n; i++)
    fo << d[i] << ' ';
	return 0;
}