import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;;

public class Main {
	
	private static int n, m, s;
	private static List<List<Integer>> adj;
	private static int cost[];
	
	public static void readFile(String filename) throws IOException {
		Scanner reader = new Scanner(new FileInputStream(filename));
		n = reader.nextInt();
		m = reader.nextInt();
		s = reader.nextInt();
		adj = new ArrayList<List<Integer>>(n);
		for (int i = 0; i < n; ++i)
			adj.add(new ArrayList<Integer>());
		cost = new int[n];
		for (int i = 0; i < m; ++i) {
			int x = reader.nextInt();
			int y = reader.nextInt();
			adj.get(x-1).add(y-1);
		}
		
		reader.close();
	}
	
	public static void BFS() {
		for (int i = 0; i < n; ++i)
			cost[i] = -1;
		int[] coada = new int[10000];
		int size = 0;
		coada[size++] = s-1;
		cost[s-1] = 0;
		
		 for (int i = 0; i < size; ++i) {
			int node = coada[i];
			for(int j : adj.get(node)) {
				if (cost[j] == -1) {
					coada[size++] = j;
					cost[j] = cost[node]+1;
				}
			}
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		readFile("bfs.in");
		BFS();
		
		PrintWriter writer = new PrintWriter("bfs.out");
		for (int i = 0; i < n; ++i) {
			writer.write(String.valueOf(cost[i])+ " ");
		}
		writer.close();
	}
}