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

using namespace std;


string const inFile = "bfs.in";
string const outFile = "bfs.out";

unsigned const MAXVAL = (1u << 31) - 1;


ifstream _read(inFile);
ofstream _write(outFile);


void Read(unsigned &n, unsigned &m, unsigned &start, vector<vector<unsigned>> &nodes) {
    _read >> n;
    _read >> m;
    _read >> start;

    --start;

    nodes.resize(n);

    unsigned node1;
    unsigned node2;

    for (unsigned i = 0; i < m; ++i) {
        _read >> node1;
        _read >> node2;

        nodes[node1 - 1].push_back(node2 - 1);
    }
}


void Write(vector<unsigned> const &depth) {
    for (unsigned i = 0; i < depth.size(); ++i) {
        if (depth[i] == MAXVAL) {
            _write << "-1 ";
        }
        else {
            _write << depth[i] << ' ';
        }
    }
}


void BFS(vector<vector<unsigned>> const &nodes, unsigned const start) {
    vector<bool> vis(nodes.size());
    vector<unsigned> depth(nodes.size(), MAXVAL);
    queue<unsigned> _queue;
    unsigned node;

    _queue.push(start);
    vis[start] = true;

    depth[start] = 0;

    while (_queue.empty() == false) {
        node = _queue.front();
        _queue.pop();

        for (unsigned i = 0; i < nodes[node].size(); ++i) {
            if (vis[nodes[node][i]] == true) {
                continue;
            }

            _queue.push(nodes[node][i]);
            vis[nodes[node][i]] = true;

            depth[nodes[node][i]] = depth[node] + 1;
        }
    }

    Write(depth);
}


int main() {
    unsigned n;
    unsigned m;
    unsigned start;
    vector<vector<unsigned>> nodes;

    Read(n, m, start, nodes);

    BFS(nodes, start);

    return 0;
}