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

using namespace std;

struct Node
{
    int v;
    Node* next;
    Node(int v, Node* next = nullptr) : v(v), next(next) {}
};

vector<int> bfs(const int& start, const vector<Node*>& graph)
{
    vector <int> visited(graph.size(), -1);
    visited[start] = 0;
    queue <int> q;
    q.push(start);

    while (!q.empty())
    {
        int parent = q.front();
        Node* p = graph[parent];
        q.pop();

        while (p != nullptr)
        {
            int child = p->v;
            if (visited[child] == -1)
            {
                visited[child] = visited[parent] + 1;
                q.push(child);
            }
            p = p->next;
        }
    }
    return visited;
}

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

    int n, m, s;
    fin >> n >> m >> s;

    vector<Node*> graph(n + 1, nullptr);

    for (int i = 0; i < m; ++i)
    {
        int v, w;
        fin >> v >> w;
        graph[v] = new Node(w, graph[v]);
    }

    vector<int> distance = bfs(s, graph);
    for (size_t i = 0; i < distance.size(); ++i)
    {
        fout << distance[i] << " ";
    }
    fout << endl;

    return 0;
}