/*
ID: i.adri1
PROG: bfs
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <assert.h>
#include <math.h>
#include <string.h>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

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

class graf {
    int n;
    vector<int> *vec;
public:
    graf(int n) {
        this->n = n;
        vec = new vector<int>[n];
    }
    void adauga_arc(int x, int y) {
        vec[x].push_back(y);
    }
    int* bfs(int S) {
        int* dist = new int[n];
        for (int i = 0; i < n; i++)
            dist[i] = -1;   /* also means unvisited */
        queue<int> q;
        q.push(S);
        dist[S] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int j = 0; j < vec[x].size(); j++) {
                if (dist[vec[x][j]] != -1) continue;
                dist[vec[x][j]] = dist[x] + 1;
                q.push(vec[x][j]);
            }
        }
        return dist;
    }
 };

int main()
{
    int N, M, S, x, y;
    in>>N>>M>>S;
    graf G(N);
    while (M-->0) {
        in>>x>>y;
        G.adauga_arc(x-1, y-1);
    }
    int *dist = G.bfs(S-1);
    for (int i = 0; i < N; i++)
        out<<dist[i]<<" ";

    return 0;
}