#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int ANS;
const int MAX = 2*1e5 + 10;
int d[MAX];


class Graph{
	private:
		int size;
		vector<vector<int>> adj;

		void dfs_helper(int v, vector<bool>& vis);
		void bfs_helper(vector<bool>& vis, queue<int>& q);
	public:
		Graph(int sz) :size {sz}, adj {vector<vector<int>>(sz + 1)} {}

		void add_edge(int v1, int v2);
		void add_edge(int v1, int v2, int weight);
		void print();
		void dfs(int start_vertex);
		void bfs(int start_vertex);
};


//Basic utilities, add edge, add weighted edge, print to stdout etc.
void Graph::add_edge(int v1, int v2){
	adj[v1].push_back(v2);
}


void Graph::print(){
			for(int i=1; i <= size; ++i){
				cout << i << ":";
				for(auto u: adj[i])
					cout << " " << u;
				cout << "\n";
			}
		}


// The recursive dfs traversal algorithm. 
// We initialize a vector vis of visits locally and pass it by reference to prevent useless copying.
void Graph::dfs(int start_vertex){
	vector<bool> vis(size);

	for(int i = start_vertex; i <= size; ++i){
		if(!vis[i]){
			dfs_helper(i, vis);
			++ANS;
		}
	}
}


void Graph::dfs_helper(int v, vector<bool>& vis){
	vis[v] = 1;

	for(auto u: adj[v])
		if(!vis[u])
			dfs_helper(u, vis);
}

// Bfs traversal algorithm.
// As before we maintain a visits vector and a queue of the next vertices to visit.
void Graph::bfs(int start_vertex){
	vector<bool> vis(size);
	queue<int> q;
	d[start_vertex] = 0;
	q.push(start_vertex);
	bfs_helper(vis, q);
}


void Graph::bfs_helper(vector<bool>& vis, queue<int>& q){
	int v = q.front(); //starting vertex
	vis[v] = 1;

	for(auto u: adj[v]) //extend queue
		if(!vis[u]){
			q.push(u);
			vis[u] = 1;
			d[u] = d[v] + 1;
		}

	q.pop(); 
	if(!q.empty())
		bfs_helper(vis, q);
}



int main(){
	ifstream fin;
	ofstream fout;
	fin.open("bfs.in");
	fout.open("bfs.out"); 
	int n, m, u, v, s;
	fin >> n >> m >> s;
	Graph g(n);

	for(int i = 1; i <= m; ++i){
		fin >> u >> v;
		g.add_edge(u, v);
	}

	for(int i = 1; i <= n; ++i)
		d[i] = -1;

	g.bfs(s);

	for(int i = 1; i <= n; ++i)
		fout << d[i] << " ";

}