package test2;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	 static ArrayList<ArrayList<Integer>> adj;
	 static int[] visited ;
	 static int[] dist;
	
	public static void main(String[] args) throws IOException {
		 FileInputStream file = new FileInputStream("path to file");
		 BufferedReader br = new BufferedReader(new InputStreamReader(file));
		 PrintWriter out = new PrintWriter(new FileWriter("bfs.out"));
		 String line = br.readLine();
		 String[] arg = line.split(" ");
		 int n = Integer.valueOf(arg[0]);
		 int m = Integer.valueOf(arg[1]);
		 int s = Integer.valueOf(arg[2]);
		 adj = new ArrayList<ArrayList<Integer>>();
		 dist = new int[n+1];
		 for ( int i = 1 ; i <= n + 1 ;i++){
			 adj.add(new ArrayList<Integer>());
		 }
		 String[] node;
		 for (int i = 0 ; i < m ; i++){
			 line = br.readLine();
			 node = line.split(" ");
			 int x = Integer.valueOf(node[0]);
			 int y = Integer.valueOf(node[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.print("-1 ");
		 else if (n == s)
			  out.print("0 ");
		 else out.print(dist[n]+" ");
			out.close();
			br.close();
		 
	}
}