#include <iostream>     // 입력, 출력 사용
#include <vector>       // vector 사용
#include <algorithm>    // sort 사용
using namespace std;

vector<int> graph[100001];   // 각 정점의 연결된 정점 저장
int visited[100001];          // 방문 순서 저장 배열

int main() {

    int N, M, R;               // 정점 수, 간선 수, 시작 정점
    cin >> N >> M >> R;         // 입력 받기

    // 간선 입력
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;          // 두 정점 입력
        graph[a].push_back(b);  // a에서 b로 연결
        graph[b].push_back(a);  // b에서 a로 연결 (무방향)
    }

    // 작은 번호부터 방문하기 위해 정렬
    for (int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    int cnt = 1;                // 방문 순서 번호
    vector<int> st;             // DFS 스택
    vector<int> idx(N + 1, 0);  // 각 정점에서 어디까지 탐색했는지 저장

    st.push_back(R);             // 시작 정점을 스택에 넣기

    // 스택이 빌 때까지 반복
    while (!st.empty()) {

        int v = st.back();       // 스택 맨 위 정점 확인

        // 처음 방문하면 순서 저장
        if (visited[v] == 0) {
            visited[v] = cnt;
            cnt++;
        }

        bool found = false;      // 다음에 갈 정점 찾았는지 표시

        // v의 이웃 정점 탐색
        while (idx[v] < graph[v].size()) {
            int next = graph[v][idx[v]];  // 다음 이웃 정점
            idx[v]++;                     // 다음 위치로 이동

            // 아직 방문 안 했으면 스택에 넣기
            if (visited[next] == 0) {
                st.push_back(next);
                found = true;
                break;
            }
        }

        // 더 갈 곳이 없으면 뒤로 돌아가기
        if (!found) {
            st.pop_back();
        }
    }

    // 방문 순서 출력
    for (int i = 1; i <= N; i++) {
        cout << visited[i] << "\n";
    }
}