import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Se considera un graf orientat cu N varfuri si M arce.

Cerinta
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.

Date de intrare
Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S, 
cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y,
 cu semnificatia ca exista arc orientat de la x la y.

Date de iesire
In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu 
cu semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie
 parcurse de la nodul S la nodul i.
 * @author Eli
 *
 */
public class Solution {
	
	int n, m, s;
	
	// Lista de adiacenta
	ArrayList<ArrayList<Integer>> listaAdj;
	
	// Lista cu costuri
	ArrayList<Integer> costuri;
	
	// Lista paritini
	ArrayList<Integer> parents;
	
	
	Solution(){
		listaAdj = new ArrayList<ArrayList<Integer>>();
		costuri  = new ArrayList<Integer>();
		parents = new ArrayList<Integer>();
	}
	
	public void readData() throws FileNotFoundException{
		Scanner sc = new Scanner(new File("bfs.in"));
		
		n = sc.nextInt();
		m = sc.nextInt();
		s = sc.nextInt();
		
		// Initializare costuri si liste adiacenta
		for(int i = 0 ; i < n ; i ++){
			costuri.add(-1);
			listaAdj.add(new ArrayList<Integer>());		
			parents.add(i);
		}
		
		
		// Formare graf
		for(int i = 0 ; i < m; i++){
			int nod1 = sc.nextInt();
			int nod2 = sc.nextInt();
			
			listaAdj.get(nod1-1).add(nod2);
		}	
	}
	
	public void bfs(){
		ArrayList<Integer> q = new ArrayList<Integer>();
		q.add(s);
		
		int distanta = 0 ;
		costuri.set(s-1, distanta);
	
		while(q.size() > 0){
			int node = q.get(0);
			q.remove(0);
			distanta ++;
			for(int i = 0; i < listaAdj.get(node-1).size(); i++){
				int v = listaAdj.get(node-1).get(i);
				parents.set(v-1, node);
				if(costuri.get(v-1) == -1){
					q.add(v);
					costuri.set(v-1, costuri.get((parents.get(v-1))-1) +1);
					
				}
			}
			
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		Solution s = new Solution();
		
		s.readData();
		
		s.bfs();
		
		BufferedWriter bw = new BufferedWriter(new FileWriter(new File("bfs.out")));
		for(int i=0; i<s.n; i++){
			bw.write(s.costuri.get(i)+ " ");
		}
		bw.write("\n");
		
		bw.close();
	}

}