import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {
	static int N, M, S;
	private static BufferedWriter bw;
	private static BufferedReader br;

	public class Graph {
		Map<Integer, ArrayList<Integer>> graph;
		
		public Graph(){
			graph = new HashMap<>();
		}
		
		public void addNode(int node){
			graph.put(node, new ArrayList<Integer>());
		}
		
		public void addEdge(int src, int dest) {
			graph.get(src).add(dest);
		}
		
		public ArrayList<Integer> getNeighbor(int node){
			return graph.get(node);
		}
		
		@Override
		public String toString() {
			String out = "";
			for(Integer node : graph.keySet()) {
				out += "Nodul: " + node + " ===" + graph.get(node) + "\n";
			}
			return out;
		}
	}
	
	public static void readInput(Graph g){
		try{ br = new BufferedReader(new FileReader("bfs.in"));
			// Citim datele din fisier
			String input;
			String[] parseInput;
			
			input = br.readLine();
			parseInput = input.split(" ");
			N = Integer.parseInt(parseInput[0]);
			M = Integer.parseInt(parseInput[1]);
			S = Integer.parseInt(parseInput[2]);
			
			// adaugam nodurile in graf
			for(int i = 1; i <= N; i++){
				g.addNode(i);
			}
			
			// adaugam muchiile in graf
			for(int i = 0; i < M; i++){
				input = br.readLine();
				parseInput = input.split(" ");
				
				int source, dest;
				source = Integer.parseInt(parseInput[0]);
				dest = Integer.parseInt(parseInput[1]);
				g.addEdge(source, dest);
			}
		} 
		catch (Exception e) {
			e.printStackTrace();
		}
		
	}
	
	public static int[] doBfs(Graph g, int source){
		int distances[] = new int[N];
		Queue<Integer> q = new LinkedList<>();
		
		for(int i = 0; i < N; i++){
			distances[i] = -1;
		}
		
		distances[source - 1] = 0;
		q.add(source);
		
		while(!q.isEmpty()){
			int node = q.poll();
			
			
			for(int neighbor : g.getNeighbor(node)) {
				if(distances[neighbor - 1] == -1) {
					distances[neighbor - 1] = distances[node - 1] + 1;
					q.add(neighbor);
				}
			}
		}
		
		return distances;
	}
	public static void main(String []args){
		Main b = new Main();
		Graph g = b.new Graph();
		int[] distances;
		readInput(g);

		distances = doBfs(g, S);		
		try{bw = new BufferedWriter(new FileWriter("bfs.out"));
		
			for(int i = 0; i < N; i++){
				bw.write(distances[i] + " ");
				bw.flush();
			}
		}
		catch (Exception e) {
			e.printStackTrace();
		}
	}
}