package test2;

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

public class Main {
	 static ArrayList<ArrayList<Integer>> adj;
	 static int[] visited ;
	 static int[] dist;
	
	public static void main(String[] args) throws IOException {
		 Scanner br= new Scanner(new BufferedInputStream(new FileInputStream("bfs.in")));
		 PrintStream out = new PrintStream(new FileOutputStream("bfs.out"));
		 
		 int n = br.nextInt();
		 int m =  br.nextInt();
		 int s =  br.nextInt();
		 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++){
			 int x =  br.nextInt();
			 int y =  br.nextInt();
			 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();
		 
	}
}