import java.io.*;
import java.util.*;

public class Main {
	 static ArrayList<ArrayList<Integer>> adj;
	 static int[] visited ;
	 static int[] dist;
	
	public static void main(String[] args) throws IOException {
		 BufferedReader bf = new BufferedReader(new FileReader("bfs.in"));
		 PrintStream out = new PrintStream(new FileOutputStream("bfs.out"));
	     String tmp[] = bf.readLine().split(" ");
	     int n = Integer.parseInt(tmp[0]);
	     int m = Integer.parseInt(tmp[1]);
	     int s = Integer.parseInt(tmp[2]); 
	
		 adj = new ArrayList<ArrayList<Integer>>();
		 dist = new int[n+1];
		 for ( int i = 1 ; i <= n + 1 ;i++)
			 adj.add(new ArrayList<Integer>());
		 
		 for (int i = 0 ; i < m ; i++){
			 tmp = bf.readLine().split(" ");
			 int x =  Integer.parseInt(tmp[0]);
			 int y =  Integer.parseInt(tmp[1]);
			 adj.get(x).add(y);
			 }
		 
		 visited = new int[n + 1];
		 visited[s] = 1;
		 Queue<Integer> q = new LinkedList<Integer>();
		 q.add(s);
		 dist[s] = 0;
		 while (q.isEmpty() == false){
			 Integer p = q.poll();
			 
			 for (Integer x : adj.get(p))
				 if (visited[x] != 1){
					 dist[x] = dist[p] + 1;
					 q.add(x);
					 visited[x] = 1;
				 }	 
		 }
		 for (int i = 1; i <= n - 1 ; i++)
			 if (dist[i] == 0 && i != s)
				 out.print("-1 ");
			 else if (i == s)
				  out.print("0 ");
			 else out.print(dist[i]+" ");
				 
		 if (dist[n] == 0 && n != s)
			 out.println("-1 ");
		 else if (n == s)
			  out.println("0 ");
		 else out.println(dist[n]+" ");
			out.close();
			bf.close();
		 
	}
}