#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#define NMAX 100003

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int dist[NMAX];

class Graph {

	int nodes, edges, start_node;
	vector<int>* adj;
	bool oriented = true;

public:

	Graph(int nodes = 0, int edges = 0, int start_node = 0,bool oriented = true) : 
		nodes(nodes), edges(edges),start_node(start_node),oriented(oriented){
		adj = new vector<int>[nodes+1];
	}
	~Graph() {
		delete[] adj;
	}

	void set_nodes(int n) {
		nodes = n;
	}
	void set_edges(int n) {
		edges = n;
	}
	void set_start_node(int n) {
		start_node = n;
	}

	void set_oriented(bool x) {
		oriented = x;
	}
	
	int get_nodes() {
		return nodes;
	}
	int get_edges() {
		return edges;
	}
	int get_start_node() {
		return start_node;
	}
	bool get_oriented() {
		return oriented;
	}

	void set_graph() {
		for (int i = 1; i <= edges; i++) {
			int x, y;
			fin >> x >> y;
			adj[x].push_back(y);
		}

	}
	void show_graph() {
		for (int i = 1; i <= nodes; i++) {
			cout << i << ":";
			for (int j = 0; j < adj[i].size(); j++) {
				cout << adj[i][j] << ' ';
			}
			cout << '\n';
		}
	}

	void get_distances() {
		bfs();
		for (int i = 1; i < nodes + 1; i++) {
			fout << dist[i] - 1 << ' ';
		}
	}
	void bfs() {
		queue<int> que;
		que.push(start_node);
		dist[start_node] = 1;

		while (!que.empty()) {
			int node = que.front();
			que.pop();
			for (int neighbor : adj[node]) {
				if (!dist[neighbor]) {
					dist[neighbor] = 1 + dist[node];
					que.push(neighbor);
				}
			}
		}

	}
};


int main()
{
	int N, M, S;

	fin >> N >> M >> S;

	Graph g(N, M, S);
	g.set_graph();
	g.show_graph();


	g.get_distances();
	return 0;

}