#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 100000
#define MMAx 1000000

int n, m, s; 

using namespace std;

vector<int> adj_list[NMAX + 1];
queue<int> coada;
int cost[NMAX + 1], visited[NMAX + 1];



int main() {
 
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
     
    scanf("%d %d %d\n", &n, &m, &s);


    // Create adjiacency list
    for (int i = 0; i < m; i++) {
    	int start_edge, end_edge;
    	scanf("%d %d\n", &start_edge, &end_edge);
    	adj_list[start_edge].push_back(end_edge);
    }

    // cost -1 
    for (int i = 1; i <= n; i++) {
    	cost[i] = -1;
    }

    // first node
	coada.push(s);
	cost[s] = 0;
	visited[s] = 1;
	// go to the next node unvisited and add all its neighbours
	while (!coada.empty()) {
		int next = coada.front();
		coada.pop();
		for (vector<int>::iterator it = adj_list[next].begin(), end = adj_list[next].end(); it != end; ++it) {
			if (visited[*it] == 0) {
				cost[*it] = cost[next] + 1;
				coada.push(*it);
			}	
		}
	}

    for (int i = 1; i <= n; i++) {
    	printf("%d ", cost[i]);
    }
    printf("\n");

    return 0;
}