#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

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


class Graph
{
private:
	bool m_oriented;

	int m_nrNodes;
	int m_nrEdges;
	
	vector <int> m_nodes;
	vector < vector <int> > m_neighborList;

	void BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode = 0);


public:
	Graph(int nrNodes = 0, int nrEdges = 0, bool oriented = false);
	~Graph() {}

#pragma region Getters&Setters
	void setOrientation(bool orientation)
	{
		m_oriented = orientation;
	}
	void setNrNodes(int nrNodes)
	{
		m_nrNodes = nrNodes;
	}
	void setNrEdges(int nrEdges)
	{
		m_nrEdges = nrEdges;
	}

	bool getOrientation()
	{
		return m_oriented;
	}
	int getNrNodes()
	{
		return m_nrNodes;
	}
	int getNrEdges()
	{
		return m_nrEdges;
	}
#pragma endregion

	void buildNeighborList(istream& input);

	vector<int> minimalDistances(int startNode = 0);
};

Graph::Graph(int nrNodes, int nrEdges, bool oriented)
{
	m_nrNodes = nrNodes;
	m_nrEdges = nrEdges;
	m_oriented = oriented;

	for (int i = 0; i < nrNodes; i++)
	{
		vector <int> emptyVector;
		m_neighborList.push_back(emptyVector);
	}
}

void Graph::buildNeighborList(istream& input) 
{         
	for (int i = 0; i < m_nrEdges; i++) 
	{
		int node1, node2;
		input >> node1 >> node2;

		node1--;
		node2--;

		m_neighborList[node1].push_back(node2);

		if (m_oriented == false) 
		{
			m_neighborList[node2].push_back(node1);
		}
	}
}

void Graph::BFS(vector<bool>& visitedNodes, vector<int>& distances, int startNode)
{
	queue<int> nodeOrder;

	nodeOrder.push(startNode);
	distances[startNode] = 0;

	while (nodeOrder.empty() == false)
	{
		int currentNode = nodeOrder.front();
		visitedNodes[currentNode] = true;

		for (auto neighbor : m_neighborList[currentNode])
		{
			if (visitedNodes[neighbor] == false)
			{
				nodeOrder.push(neighbor);
				distances[neighbor] = distances[currentNode] + 1;
				visitedNodes[neighbor] = true;
			}
		}

		nodeOrder.pop();
	}
}

vector<int> Graph::minimalDistances(int startNode)
{
	vector <bool> visited(m_nrNodes, false);
	vector <int> distances(m_nrNodes, -1);

	BFS(visited, distances, startNode);

	return distances;
}



int main()
{
	int nrNodes, nrEdges, startNode;
	vector <int> distances;

	fin >> nrNodes >> nrEdges >> startNode;
	startNode--;

	Graph graph(nrNodes, nrEdges, true);

	graph.buildNeighborList(fin);
	distances = graph.minimalDistances(startNode);

	for (auto distance : distances)
	{
		fout << distance << " ";
	}

	fin.close();
	fout.close();

	return 0;
}