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

class FastScanner {
    private BufferedReader br;
    private StringTokenizer st;

    public FastScanner(InputStream stream) {
        br = new BufferedReader(new InputStreamReader(stream));
    }

    private String next() {
        while (st == null || !st.hasMoreTokens()) {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (line == null)
                return null;
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
	private static List<List<Integer>> G;
	private static int V;
	
	private static int[] BFS(final int source) {
		int[] distances = new int[V];
		Arrays.fill(distances, -1);
		Queue<Integer> queue = new LinkedList<Integer>();
		distances[source] = 0;
		queue.add(source);
		while (!queue.isEmpty()) {
			int x = (int)queue.remove();
			for (int y: G.get(x)) {
				if (distances[y] == -1) {
					distances[y] = distances[x] + 1;
					queue.add(y);
				}
			}
		}
		return distances;
	}
	
	private static void addEdge(final int from, final int to) {
		G.get(from).add(to);
	}
	
	public static void main(String[] args) throws IOException {
		FastScanner reader = new FastScanner(new FileInputStream("bfs.in"));
		V = reader.nextInt();
		G = new ArrayList<List<Integer>>(V);
		for (int x = 0; x < V; ++x)
			G.add(new ArrayList<Integer>());
		int edgeCount = reader.nextInt();
		int source = reader.nextInt() - 1;
		for (; edgeCount > 0; --edgeCount) {
			int from = reader.nextInt() - 1;
			int to = reader.nextInt() - 1;
			addEdge(from, to);
		}
		
		int[] distances = BFS(source);
		
		PrintWriter writer = new PrintWriter("bfs.out");
		for (int x = 0; x < V; ++x)
			writer.write(distances[x] + " ");
		writer.write("\n");
		writer.close();
	}
}