package bfs;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main 
{
	public static void bfs(int node, ArrayList<ArrayList<Integer>> adjacents) throws IOException
	{
		Queue<Integer> q = new ArrayDeque<Integer>();
		
		int[] costs = new int[adjacents.size()];
		
//		for (int i = 1;i < costs.length; i++)
//			costs[i] = -1;
		
		boolean[] visited = new boolean[costs.length];
		
		costs[node] = 0;
		visited[node] = true;
		
		q.add(node);
		
		int crtNode = -1;
		
		
		while (!q.isEmpty())
		{
			
			crtNode = q.poll();
			
//			System.out.println("crtNode " + crtNode);
			
			visited[crtNode] = true;
			
			for (int nextNode : adjacents.get(crtNode))
			{
				if (visited[nextNode])
					continue;
				
				if (costs[crtNode] + 1 < costs[nextNode] || costs[nextNode] == 0)
					costs[nextNode] = costs[crtNode] + 1;
				q.add(nextNode);
			}
			
//			System.out.println(q);
		}
		
		PrintWriter writer = new PrintWriter("bfs.out");
		
		for (int i = 1; i < costs.length; i++)
			writer.write((visited[i] ? costs[i] : -1) + " ");
		
		writer.close();
	}
	
	
	public static void main(String[] args) throws IOException
	{
		Scanner scanner = new Scanner(new FileInputStream("bfs.in"));
		
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int s = scanner.nextInt();
		
		ArrayList<ArrayList<Integer>> adjacents = new ArrayList<ArrayList<Integer>>(n);
		
		for (int i = 1; i <= n+1; i++)
			adjacents.add(new ArrayList<Integer>());
		
		int x, y;
		
		for (int i = 0; i < m; i++)
		{
			x = scanner.nextInt();
			y = scanner.nextInt();
			
			adjacents.get(x).add(y);
		}
		
		
		bfs(s, adjacents);
		
		
	}
}