#include <bits/stdc++.h>

using namespace std;

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

class Graph
{
private:

    int verticesNo;
    int edgesNo;
    bool oriented;
    vector<vector<int>> adjacencyList;


public:

    Graph();
    Graph(int verticesNo, int edgesNo, bool oriented);
    void bfs(int start);

    virtual ~Graph();

};
Graph::Graph()
{
    verticesNo = edgesNo = oriented = 0;
    this->adjacencyList.clear();
}
Graph::Graph(int verticesNo, int edgesNo, bool oriented)
{
    this->verticesNo = verticesNo;
    this->edgesNo = edgesNo;
    this->oriented = oriented;

    this->adjacencyList.resize(verticesNo + 1);

    int vertex1, vertex2;
    for(int i = 0; i < this->edgesNo; i++)
    {
        fin>>vertex1>>vertex2;
        this->adjacencyList[vertex1].push_back(vertex2);
        if(this->oriented == false)
            this->adjacencyList[vertex2].push_back(vertex1);
    }

}
Graph::~Graph()
{
        this->adjacencyList.clear();
}
void Graph::bfs(int start)
{
    int n = this->verticesNo;
    vector<int> visited;
    vector<int> distances;
    queue<int> order;
    order.push(start);

    for(int i = 0; i <= n; i++)
    {
        visited.push_back(0);
        distances.push_back(-1);
    }
    distances[start] = 0;
    visited[start] = 1;

    while(!order.empty())
    {
        int current = order.front();
        int sz = adjacencyList[current].size();

        order.pop();

        for(int i = 0; i < sz; i++)
        {
            int temp = adjacencyList[current][i];

            if(visited[temp] == 0)
            {
                visited[temp] = 1;
                order.push(temp);
                distances[temp] = distances[current]+1;
            }
        }

    }

    for(int i = 1; i < distances.size(); i++)
        fout<<distances[i]<<" ";

}



int main()
{
    int N,M,S;
    fin>>N>>M>>S;
    Graph bf(N,M,1);
    bf.bfs(S);



    return 0;
}