import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[][] graphs = new int[N + 1][M + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graphs[a][b] = 1;
            graphs[b][a] = 1;
        }
        br.close();

        // 방문 여부를 저장 할 배열
        boolean[] isVisited = new boolean[N + 1];

        // 방문 순서를 저장할 배열
        int[] visitOrder = new int[N + 1];

        bfs(graphs, isVisited, R, visitOrder);

        StringBuilder sb = new StringBuilder();
        // 1부터 시작이므로 기본 for 문 사용
        for (int i = 1; i <= N; i++) {
            sb.append(visitOrder[i]).append("\n");
        }

        System.out.println(sb);
    }

    public static void bfs(int[][] graph,
                           boolean[] visited,
                           int start,
                           int[] visitOrder) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        visited[start] = true; // 시작 정점을 방문했다고 표시
        int order = 1;

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            visitOrder[vertex] = order++;

            // 현재 정점과 인접한 모든 정점을 확인
            for (int i = 1; i < graph.length; i++) {
                // 인접하고 아직 방문하지 않은 정점이 있다면
                if (graph[vertex][i] == 1 && !visited[i]) {
                    visited[i] = true; // 해당 정점을 방문했다고 표시
                    queue.offer(i); // 큐에 추가
                }
            }
        }
    }
}