#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
    bool isVisited;
    int cost;
    vector<int> edges;

    Node() :
        isVisited(false),
        cost(-1),
        edges()
    {
    }
};

void BFS(vector<Node> &nodes, int s)
{
    queue<int> q;

    nodes[s].isVisited = true;
    nodes[s].cost = 0;
    q.push(s);

    while(!q.empty())
    {
        int parentIndex = q.front();
        q.pop();

        for(int index : nodes[parentIndex].edges)
        {
            if(!nodes[index].isVisited)
            {
                nodes[index].isVisited = true;
                nodes[index].cost = nodes[parentIndex].cost + 1;
                q.push(index);
            }
        }
    }
}

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

    if(!fin.is_open() || !fout.is_open())
        return 1;

    vector<Node> nodes;
    int n, m, s;
    fin >> n >> m >> s;

    for(int i = 0; i < n; i++)
        nodes.push_back(Node());

    for(int i = 0, x, y; i < m; i++)
    {
        fin >> x >> y;
        nodes[x - 1].edges.push_back(y - 1);
    }

    BFS(nodes, s - 1);

    for(size_t i = 0; i < nodes.size(); i++)
    {
        fout << nodes[i].cost << ' ';
    }

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

    return 0;
}