#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;

typedef unsigned long ulong;

#define NDEBUG

#ifdef NDEBUG
#define dbg	0 && (*((ostream *) 0))
#else
#define dbg clog
#endif

class BFS
{
	public:
		BFS(std::vector<std::vector<ulong>* >& adjacencyList, ulong nVertices, ulong sourceNode)
			:	numVertices(nVertices), source(sourceNode), adjList(adjacencyList)
		{
			costs.resize(nVertices + 1, -1);
		}
		
	public:
		void execute()
		{
			costs[source] = 0;
			bfs(source);
		}
		
		void bfs(ulong node)
		{
			std::list<ulong> queue;
			
			queue.push_back(node);
			
			
			while(!queue.empty())
			{
				ulong current = queue.front();
				queue.pop_front();
				
				std::vector<ulong> * neighbours = adjList[current];
				if(!neighbours)
					continue;
				
				for(ulong i = 0; i < neighbours->size(); i++)
				{
					ulong vertex = (*neighbours)[i];
					
					if(costs[vertex] == -1)
					{
						queue.push_back(vertex);
						costs[vertex] = costs[current] + 1;
					}
				}
			}
		}
		
		
		const std::vector<long>& getCosts() const { return costs; }
		
	private:
		ulong numVertices;
		ulong source;
		std::vector<std::vector<ulong>* >& adjList;
		std::vector<long> costs;
};

int main(int argc, char * argv[]) 
{
	
	const char * inFile = "bfs.in";
	const char * outFile = "bfs.out";
	
	ifstream fin(inFile);
	
	#ifndef NDEBUG
		if(!fin || !fout) 
		{
			cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
			return -1;
		}
	#endif
	
	/**
	 *	Read the data in.
	 */
	ulong n, m, source;
	fin >> n >> m >> source;
	
	std::vector<std::vector<ulong>* > adjList;
	adjList.resize(n + 1, NULL);
	
	ulong x, y;
	for(ulong i = 0; i < m; i++)
	{
		fin >> x;
		fin >> y;
		
		if(adjList[x] == NULL)
		{
			adjList[x] = new std::vector<ulong>();
		}
		
		adjList[x]->push_back(y);
	}
	
	/**
	 *	Solve the problem.
	 */
	BFS bfs(adjList, n, source);
	bfs.execute();
	
	const std::vector<long>& costs = bfs.getCosts();
	
	ofstream fout(outFile);
	for(std::vector<long>::const_iterator it = costs.begin() + 1;
		it != costs.end(); ++it)
	{
		fout << *it << " ";
	}
	
	/**
	 *	Cleanup!
	 */
	for(ulong i = 0; i < adjList.size(); i++)
	{
		if(adjList[i] != NULL)
			delete adjList[i];
	}
	
	fout.close();
	fin.close();
	
	return 0;
}