#include <fstream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

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

void ReadMatrix(vector<vector<int>> &matrix, int M, int N, bool bidirectional)
{
    vector<vector<int>> newmatrix(N+1, vector<int>(N+1, 0));
    matrix = newmatrix;
    for(int i=1; i<=M; i++)
    {
        int in, out;
        fin >> in >> out;
        matrix[in][out] = true;
        if(bidirectional) matrix[out][in] = 1;
    }
}

void PrintMatrix(vector<vector<int>> matrix, int N)
{
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cout << matrix[i][j] << ' ';
        }
        cout<<'\n';
    }
}

void ReadList(vector<vector<int>> &matrix, int N, int M, bool bidirectional)
{
    vector<vector<int>> newmatrix(N+1, vector<int>(0,0));
    matrix=newmatrix;
    for(int i=1; i<=M; i++)
    {
        int in, out;
        fin >> in >> out;
        matrix[in].push_back(out);
        if(bidirectional) matrix[out].push_back(in);
    }
}

void PrintList(vector<vector<int>> matrix, int N)
{
    for(int i=1; i<=N; i++)
    {
        cout << i << ": {";
        int size = matrix[i].size();
        for(int j=0; j<size; j++)
        {
            cout << matrix[i][j] << ", ";
            
        }
        cout << "}\n";
    }
}

void MatrixToList(vector<vector<int>> &matrix)
{
    int N = matrix.size()-1;
    vector<vector<int>> list(N+1, vector<int>(0,0));

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            if(matrix[i][j] != false) list[i].push_back(j);

        }
    }
    matrix=list;

}
void ListToMatrix(vector<vector<int>> &list)
{
    int N = list.size()-1;
    vector<vector<int>> matrix(N+1, vector<int>(N+1, 0));

    for(int i=1; i<=N; i++)
    {
        int width = list[i].size();
        for(int j=0; j<width; j++)
        {
            matrix[i][list[i][j]] = true;
        }
    }
    list=matrix;
}

vector<int> Path(vector<vector<int>> list, int root)
{
    queue<pair<int, int>> q;
    vector<bool> visited(list.size(), false);
    vector<int> depths(list.size(), -1);

    q.push(make_pair(root, 1));
    visited[root] = true;
    depths[root] = 0;

    while(q.size() > 0)
    {
        pair<int,int> info = q.front();
        int node = info.first;
        int depth = info.second;
        q.pop();

        int width = list[node].size();
        for(int i = 0; i<width; i++)
        {
            int target = list[node][i];
            if( !visited[target] )
            {
                q.push(make_pair(target, depth+1));
                visited[target] = true;

                depths[target]=depth;
            }
        }

    }
    return depths;
}

int main()
{
    vector<vector<int>> matrix;

    int N, M;
    fin >> N >> M;

    int target;
    fin>>target;

    ReadMatrix(matrix, N, M, true);

    MatrixToList(matrix);

    //PrintList(matrix, N);
    vector<int> result = Path(matrix, target);

    for(int i=1; i<=N; i++)
    {
        cout<<result[i] << ' ';
    }
}