import java.awt.im.InputContext;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;

/*Fiind dat un nod S, sa se determine, pentru fiecare nod X, 
 * numarul minim de arce ce trebuie parcurse pentru a ajunge 
 * din nodul sursa S la nodul X.
 */
public class p1 {
	public static void main(String[] args) {
		Graph g = new Graph();
		g.readData();
		
		//AFISARE
		for(int i = 0 ; i < g.getNodeCount(); i++){
			System.out.print("Nodul " + i + ": ");
			for(int j = 0; j < g.edges.get(i).size(); j++){
				System.out.print(g.edges.get(i).get(j)._id + " ");
			}
			System.out.println();
		}
		
		//BFS
		for(int i = 0; i < g.getNodeCount(); i++){
			g.getNodes().get(i)._father = null;
			g.getNodes().get(i)._d = -1;
			g.getNodes().get(i)._culoare = 0; //Alb
		}
		ArrayList<Node> coada = new ArrayList<>();
		g.getNodes().get(2)._d = 0;
		coada.add(g.getNodes().get(g.S));
		g.getNodes().get(g.S)._culoare = -1;//GRI
		
		while(coada.isEmpty() == false){
			Node u = coada.remove(0);
			
			for(int i = 0; i < g.edges.get(u._id).size(); i++){
				Node v = g.edges.get(u._id).get(i);
				if(v._culoare == 0){
					v._d = u._d + 1;
					v._father = u;
					v._culoare = -1;
					coada.add(v);
				}
			}
			
			u._culoare = 1;
			
			
		}
		
		/*for(int i = 1; i < g.getNodeCount();i++){
			System.out.print(g.getNodes().get(i)._d + " ");
		}*/
		
		BufferedWriter bf = null;
		try{
			FileWriter file = new FileWriter("bfs.out");
			bf = new BufferedWriter(file);
			for(int i = 1; i < g.getNodeCount();i++){
				bf.write(Integer.toString(g.getNodes().get(i)._d));
				bf.write(" ");
			}
				
		}catch(IOException e) {
			e.printStackTrace();
		}finally {
			try {
				bf.close();
			}catch (IOException e) {
				e.printStackTrace();
			}
		}
		
	}
}
	class Node {
	
		String _name;
		int _id;
		Node _father; //Parintele unui nod.
		int _culoare; //Culoarea unui nod.
		int _d; //Timpul de descoperire.
		int _f; //Timpul de finalizare.
	
		public Node(String name, int id)
		{
			_name = name;
			_id   = id;
		}
	
		public Node( int id )
		{
			_name = "";
			_id = id;
			_culoare = 0; //Nod alb.
			_d = 0;
			_f = 0;
		}
	
		//Intorc id-ul unui nod.
		public int getId()
		{
			return _id;
		}
		
		//Intorc parintele unui nod.
		public Node getParent()
		{
			return _father;
		}
	}
	
	
	class Graph {

		ArrayList< Node > nodes;
		ArrayList< ArrayList< Node > > edges;

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

		//Intorc numarul de noduri ale grafului.
		public int getNodeCount()
		{
			return nodes.size();
		}

		//Adaug o muchie
		public void insertEdge( Node node1, Node node2 )
		{
			edges.get( node1.getId() ).add( node2 );
		}

		//Adaug un nod.
		public void insertNode( Node node )
		{
			nodes.add( node );
			edges.add( new ArrayList< Node >() );
		}

		public ArrayList< Node > getNodes()
		{
			return nodes;
		}

		public ArrayList< Node > getEdges( Node node )
		{
			return edges.get( node.getId() );
		}

		public int N = 0; //Retin numarul de buncare.
		public int M = 0; //Retin numarul de portaluri.
		public int S = 0; 
		public void readData(){
			
			BufferedReader reader = null;
			//Citesc din fisier.
			try {
				File file = new File("bfs.in");
				//InputStreamReader file = new InputStreamReader(System.in);
			   // reader = new BufferedReader(file);
				reader = new BufferedReader(new FileReader(file));
				String linie; //Cu aceasta variabila citesc linie cu linie din fiser.
				
				//Citesc prima linie. 
				linie = reader.readLine(); 
				int[] numerePrimaLinie = new int[3];
				String[] numere = linie.trim().split("\\s+");
				for (int i = 0; i < 3; i++) {
					numerePrimaLinie[i] = Integer.parseInt(numere[i]);
				}
				
				//Retin cele 2 numere.
				N = numerePrimaLinie[0];
				M = numerePrimaLinie[1];
				S = numerePrimaLinie[2];
				
				int numNodes = N;
				int numEdges = M;
				
				//Adaug nodurile.
				for( int i = 0; i <= numNodes; ++i )
				{
					Node new_node = new Node(i);
					insertNode( new_node );
				}
					
				//Adaug muchiile.
				while (numEdges > 0 ) {
					linie = reader.readLine();
					numere = linie.trim().split("\\s+");
					insertEdge( nodes.get( Integer.parseInt(numere[0]) ), nodes.get( Integer.parseInt(numere[1]) ) );
					//insertEdge( nodes.get( Integer.parseInt(numere[1]) ), nodes.get( Integer.parseInt(numere[0]) ) );
					numEdges--; 
				}
				
			} catch (IOException e) {
			e.printStackTrace();
			}finally {
				try {
					reader.close();
				}catch (IOException e) {
				e.printStackTrace();
				}
			}
		}
	}