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 Bfs {
	
	private static int n, m, s;
	private static List<List<Integer>> adj;
	private static int cost[];
	private static Queue<Integer> queue;
	
	public static void readFile(String filename) throws FileNotFoundException {
		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];
		queue = new LinkedList<Integer>();
		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;
		queue.offer(s-1);
		cost[s-1] = 0;
		
		while (!queue.isEmpty()) {
			int node = queue.poll();
			for(int j : adj.get(node)) {
				if (cost[j] == -1) {
					queue.add(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();
	}
}