import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	static ArrayList< Integer > []L = new ArrayList[100004];
	static int[] sol = new int [100004];
	static public void main(String []args) throws IOException
	{
		Scanner in = new Scanner(new FileInputStream("bfs.in"));
		PrintWriter out = new PrintWriter("bfs.out");
		int n = in.nextInt(),x, y;
		int m = in.nextInt();
		int node = in.nextInt();
		for(int i=1;i<=n;++i)
		{
			L[i] = new ArrayList();
			sol[i] = -1;
		}
		while(m-->0)
		{
			x = in.nextInt();
			y = in.nextInt();
			L[x].add(y);
		}
		sol[node] = 0;
		Queue <Integer > Q = new LinkedList <Integer>();
		for(Q.add(node); Q.size() > 0;)
		{
			node = Q.poll();
			for(Integer k : L[node])
				if(sol[k] == -1)
				{
					sol[k] = sol[node]+1;
					Q.add(k);
				}
			
		}
		for(int i=1;i<=n;++i)
			out.print(String.valueOf(sol[i])+" ");
		in.close();
		out.close();
	}
}