#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(int start, int count, vector<int>* vec, bool* visited, int* order) {
	visited[start] = true;
	order[start] = count;

	for (int i = 0; i < vec[start].size(); i++) {
		int next = vec[start][i];

		if (!visited[next]) {
			count++;
			DFS(next, count, vec, visited, order);
		}

	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, R;
	cin >> N >> M >> R;

	vector<int>* graph = new vector<int>[N];
	int* order = new int[N]();
	bool* visited = new bool[N]();

	while (M--) {
		int u, v;
		cin >> u >> v;
		graph[u - 1].push_back(v - 1);
		graph[v - 1].push_back(u - 1);
	}

	for (int i = 0; i < N; i++)
		sort(graph[i].begin(), graph[i].end());

	DFS(R - 1, 1, graph, visited, order);

	for (int i = 0; i < N; i++)
		cout << order[i] << "\n";

	delete[] graph;
	delete[] order;
	delete[] visited;

	return 0;
}