import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;


class Graph {

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

	/**
	 * 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 Graph() {
		edges = new ArrayList<>();
	}

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

	/**
	 * 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;
	}
	
	public int getSource() {
		return source;
	}

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

	/**
	 * Function to read all the tests
	 *
	 * Input Format:
	 * N M
	 * Nodei Nodej Costij			   -- list of edges
	 * ...
	 * where
	 * N = Number of Nodes
	 * M = Number of Edges
	 * Costij = cost of edge from i to j, as well as from j to i
	 * @param scanner
	 */
	public void readData(Scanner scanner) {

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

		for (int i = 0; i < numNodes + 1; i++) {
			insertNode(i);
		}

		for (int edgeIdx = 1; edgeIdx <= numEdges; edgeIdx++) {
			int node1 = scanner.nextInt();
			int node2 = scanner.nextInt();

			insertEdge(node1, node2);
		}
	}

	public String toString() {

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

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

			for (Integer edge : edges.get(n)) {
				sb.append(edge);
                sb.append(" | ");
			}

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

		return sb.toString();
	}
}


public class Main {

	final static String PATH = "test.txt";
	public static int cost; // Costul total al AMA.

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new File(PATH));

		// create the graph and read the data
		Graph g = new Graph();
		g.readData(sc);
		// debugging: print the graph
		//System.out.println(g);
		int source = g.getSource();
		
		int[] distance = bfs(g, source);
		int numNodes = g.getNodeCount();
		
		for(int i = 1; i <= numNodes; i++) {
			if(distance[i] == 0 && i != source)
				System.out.print("-1 ");
			else
				System.out.print(distance[i] + " ");
		}

		sc.close();
	}
	
	public static int[] bfs(Graph g, int source) {
		int numNodes = g.getNodeCount();
		int[] color = new int[numNodes + 1];
		int[] distance = new int[numNodes + 1];
		Queue<Integer> q = new LinkedList<>();
		//Adaug nodul initial in coada;
		q.add(source);
		color[source] = 1; //gri 
		distance[source] = 0;
		
		while(!q.isEmpty()) {
			int u = q.poll();
			List<Integer> succs = g.getEdges(u);
			
			for(Integer v : succs) {
				if(color[v] == 0) { //nod alb
					distance[v] = distance[u] + 1;
					color[v] = 1;
					q.add(v);
				}
			}
			
			color[u] = 2; //nodul devine negru.
		}
		
		
		return distance;
	}
}