#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 10001

using namespace std;

bool visited[N];
	
//ifstream fin("dfs.in");
//ofstream fout("dfs.out");
	
ifstream fin("bfs.in");
ofstream fout("bfs.out");
	
class Graph {
	
public:
	vector <int> adiacenta[N];
    int n_g, m_g;
    void addEdge_neorientat(int h, int t);
    void addEdge_orientat(int h, int t);
    void BFS_mininum_distances(int root);
	void DFS(int vf);
};
	
 
	
void Graph::addEdge_neorientat(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::addEdge_orientat(int h,int t)
{
     adiacenta[h].push_back(t);
}
 
	
void Graph::DFS(int vf)
{
	visited[vf] = true;
	
	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
	
}

void Graph::BFS_mininum_distances(int root)
{
        vector<int> d(n_g + 1, -1);
        queue<int> Q;
	
        d[root] = 0;
        Q.push(root);
	
        while (!Q.empty()) {
            int current = Q.front();
            Q.pop();
 
            for (auto &index : adiacenta[current]) {
                if (d[index] == -1)
                {
                    d[index] = d[current] + 1;
                    Q.push(index);
                }
            }

        }
	
        for (int i = 1; i <= n_g; ++i) {
            fout << d[i] << ' ';
        }
}

	
int main()
{
	
	int n, m, n1, n2, conexe = 0, s = 2;
	fin >> n >> m >> s;
	
	Graph g;

    g.n_g = n;
    g.m_g = m;
	
    for (int i = 1; i <= m; i++)
	{
        fin >> n1 >> n2;
        g.addEdge_orientat(n1,n2);
    }
	
    //pb 1
	// for(int i = 1; i <= n; i++){
    //     if (!visited[i])
    //     {
    //        conexe += 1;
    //        g.DFS(i);
    //     }
	// }
	//fout << conexe;

    g.BFS_mininum_distances(s);

	return 0;
	
}