//
//  main.cpp
//  bfs
//
//  Created by Ciprian Ionescu on 12/19/19.
//  Copyright © 2019 Ciprian Ionescu. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <array>
#include <queue>

#define MAX_N 100001
#define MAX_M 1000001

template <typename T>
struct Node {
    T node;
    Node *next;
};

template <typename T, size_t N, size_t M>
class Graph {
public:
    size_t size;
    
    void add(const T& x, const T& y) {
        _nodes[++size].node = y;
        _nodes[size].next = _list[x];
        _list[x] = &_nodes[size];
    }
    
    Node<T>& get_node(const T& x) {
        return *_list[x];
    }
    
    bool visited(const T& x) {
        return _visited[x];
    }
    
    void visit(const T& x) {
        _visited[x] = true;
    }
    
    void reset() {
        for (auto &it : _visited) it = false;
    }
private:
    std::array<Node<T>, M> _nodes;
    std::array<Node<T>*, N> _list;
    
    std::array<bool, N> _visited;
};

template <typename T, size_t N, size_t M>
void dfs(Graph<T, N, M>& g, const T& x) {
    g.visit(x);
    
    Node<T>* p = &g.get_node(x);
    
    while (p) {
        if (!g.visited(p->node))
            dfs(g, p->node);
        p = p->next;
    }
}

int d[MAX_N];

template <typename T, size_t N, size_t M>
void bfs(Graph<T, N, M>& g, const T& x) {
    std::queue<T> q;
    
    for (q.push(x) ; !q.empty() ; q.pop()) {
        g.visit(q.front());
        for (auto p = &g.get_node(q.front()) ; p ; p = p->next)
            if (d[p->node] == -1) q.push(p->node), d[p->node] = 1 + d[q.front()];
    }
}

Graph<int, MAX_N, MAX_M> g;

using std::cin;
using std::cout;

int main()
{
    std::ifstream fin("bfs.in");
    std::ofstream fout("bfs.out");
    
    int n, m, s, x, y;
    fin >> n >> m >> s;
    
    for (auto i = 1 ; i <= m ; i++) {
        fin >> x >> y;
        g.add(x, y);
    }
    
    for (auto i = 1 ; i <= n ; i++) d[i] = -1;
    
    d[s] = 0;
    bfs(g, s);
    
    for (auto i = 1 ; i <= n ; i++)
        fout << d[i] << ' ';
    return 0;
}