import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Main {
	
	
	static int numEdges;
	static int numNodes;
	static int source;

	static class Edge{
		int start;
		int end;
		long cost;
		
		public Edge(){
			start = 0;
			end = 0;
			cost = 0;
		}
		
		public Edge(int start,int end){
			this.start = start;
			this.end = end;
			
		}
		
		public String toString(){
			
			return "(" + " " + this.start + " " + this.end + " )";
		}


	}
	
	public static void bfs(ArrayList<ArrayList<Edge>> edge,ArrayList<Integer> nodes,int source){
		
		try {
			BufferedWriter bufferedOut = new BufferedWriter( new FileWriter("bfs.out"));
			PrintWriter out = new PrintWriter(bufferedOut);
			
		
		
		ArrayList<Integer> result = new ArrayList <Integer>();
		for (int i=0;i<numNodes;i++){
			result.add(-1);
		}

		int[] isVisited = new int[numNodes];
		for (int i=0;i<numNodes;i++)
			isVisited[i] = 0;
		
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(source);
		isVisited[source] = 0;
		result.set(source, 0);
	
		while(!q.isEmpty()){
			
			int n = q.peek();
			ArrayList<Edge> neighbour = edge.get(n);
			for (Edge e : neighbour){
				
				if (isVisited[e.end]!=1){
					isVisited[e.end] = 1;
					q.add(e.end);
					//System.out.println(e.end);
					//System.out.println(result);
					if (e.end != source)
					result.set(e.end,result.get(n) + 1);
				}
			}
			q.poll();
		}
		

		for (int i = 0 ; i < result.size() ; i++){
			out.print(result.get(i)+" ");		//scrierea in fisier
			//System.out.print(result.get(i)+" ");
		}
		
	
		out.close();
		bufferedOut.close();
	
	} catch (IOException e) {
		e.printStackTrace();
	}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		BufferedReader in = null;
		ArrayList<Integer> nodes = new ArrayList<Integer>();	//lista nodurilor
		ArrayList<ArrayList<Edge>> edges = new ArrayList<ArrayList<Edge>>();		//lista muchiilor pe care trebuie sa o pastram nesortata pt a putea face rost de muchiile alternative
	
		try {
			in = new BufferedReader(new FileReader("bfs.in"));
			String[] aux = in.readLine().split(" ");
			numNodes = Integer.parseInt(aux[0]);
			numEdges = Integer.parseInt(aux[1]);
			source = Integer.parseInt(aux[2])-1;
			
			for(int i = 0 ; i < numNodes ; i++){
				nodes.add(i);
			}
			
			for (int i=0;i<numEdges;i++)
				edges.add(new ArrayList<Edge>());
			
			for (int i = 0 ; i < numEdges ; i++){
				
				aux = in.readLine().split(" ");
				int s = Integer.parseInt(aux[0])-1;
				int e = Integer.parseInt(aux[1])-1;
				edges.get(s).add(new Edge(s,e));
			}
			
			
			
			bfs(edges,nodes,source);	//aplicam algoritmii de mai sus si memoram rezultatele intr-o lista
			
		} catch (IOException e) {
			e.printStackTrace();
		
		} finally {
			if (in != null) {
		
				try {
					in.close();
				
				} catch (IOException e) {

				}
			}
		}
		
		
	
	}
}