#include <iostream>
#include <map>
#include <vector>
#include <fstream>
using namespace std;

map <int, vector <int>> graphG;

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

int main() {
    int n, m, s;
    fin >> n >> m >> s;
    int minimumRoad[n + 1] = {0};
    while (m--) {
        int x, y;
        fin >> x >> y;
        graphG[x].push_back(y);
    }
    vector <int> bfs;
    bfs.push_back(s);
    int actualLength = 1, beg = 0, end = 0;
    while (true) {
        int nrElements = 0;
        while (beg <= end) {
            int lg = graphG[bfs[beg]].size();
            for (int i = 0; i < lg; ++i) {
                if (minimumRoad[graphG[bfs[beg]].at(i)] == 0) {
                    ++nrElements;
                    bfs.push_back(graphG[bfs[beg]].at(i));
                    minimumRoad[graphG[bfs[beg]].at(i)] = actualLength;
                }
            }
            ++beg;
        }
        end += nrElements;
        ++actualLength;
        if (!nrElements) {
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i == s) {
            fout << "0 ";
        } else {
        if (minimumRoad[i]) {
            fout << minimumRoad[i] << ' ';
        } else {
            fout << -1 << ' ';
        }
      }
    }
}
/*TESTS:

12 20 3
10 3
11 10
3 4
3 11
3 2
4 9
4 3
4 11
4 5
1 2
1 6
2 8
2 5
7 10
8 9
5 10
6 12
12 7
5 1
5 7
*/