package test2p1;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

class Graph {

	/**
	 * Total number of nodes that makes the graph
	 */
	private int numNodes;
	public int numEdges;
	public int sourceNode;

	/**
	 * The graph uses list of adjacencies for each node.
	 * The first item of the pair represents the index of the adjacent,
	 * while the second item represents the cost of the edge
	 */
	private List<List<Integer>> edges;
	public int[] alternatePath;

	public Graph() {
		edges = new ArrayList<>();
	}

	public void insertNode(int nodeIdx) {
		edges.add(new ArrayList<Integer>());
		
	}

	/**
	 * Inserts a new edge into the graph starting at 'fromNodeIdx' and
	 * ending at 'toNodeIdx', having cost value of 'cost'
	 *
	 * @param fromNodeIdx
	 * @param toNodeIdx
	 * @param cost
	 */
	public void insertEdge(int fromNodeIdx, int toNodeIdx) {
		edges.get(fromNodeIdx).add(toNodeIdx);
	}

	public int getNodeCount() {
		return numNodes + 1;
	}

	public List<Integer> getEdges(int nodeIdx) {
		return edges.get(nodeIdx);
	}

	public void readData(Scanner scanner) {

		numNodes = scanner.nextInt();
		int numEdges = scanner.nextInt();		
		sourceNode = scanner.nextInt();

		for (int i = 1; i <= numNodes + 1; i++) {
			insertNode(i);
		}
		for (int edgeIdx = 0; edgeIdx < numEdges; edgeIdx++) {
			int node1 = scanner.nextInt();
			int node2 = scanner.nextInt();
			insertEdge(node1, node2);
		}		
	}

	@Override
	public String toString() {

		StringBuilder sb = new StringBuilder("Print Graph:\n");

		for(int n = 1; n < numNodes+1; n++) {
			sb.append("OutEdges for " + n + " -> ");

			for (int edge : edges.get(n)) {
				sb.append(edge+" ");
			}

			sb.append("\n");
		}
		sb.append("\n");

		return sb.toString();
	}
}

public class Solution {

	final static String PATH = "bfs.in";
	
	public static void main(String ... args) throws IOException {
		Scanner sc = new Scanner(new File(PATH));
		// create the graph and read the data
		Graph g = new Graph();
		g.readData(sc);
		int[] cost = new int[100010];
		for(int i = 0; i < g.getNodeCount(); i++)
			cost[i] = -1;
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(g.sourceNode);
		cost[g.sourceNode] = 0;
		//System.out.println(g.sourceNode);
		while(!q.isEmpty()){
			int nod = q.poll();
			for(int v : g.getEdges(nod))
				if(cost[v]== -1){
					q.add(v);
					cost[v] = cost[nod]+1;
				}
		}
		BufferedWriter output = null;
        try {
            File file = new File("bfs.out");
            output = new BufferedWriter(new FileWriter(file));
            for( int i = 1; i < g.getNodeCount(); i++){
    			output.write(cost[i]+" ");
    		}
		} catch ( IOException e ) {
	        e.printStackTrace();
	    } finally {
	      if ( output != null ) {
	        output.close();          
	      }
	      sc.close();
	    }
		for( int i = 1; i < g.getNodeCount(); i++){
			System.out.print(cost[i]+" ");
		}
		
	}
	
}