#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#define MAX_N 100005
using namespace std;

vector<int> v[MAX_N];
int dp[MAX_N];

int main()
{
    FILE *fin = fopen("bfs.in", "r");
    FILE *fout = fopen("bfs.out", "w");
    int n, m, s;
    fscanf(fin, "%d %d %d", &n, &m, &s);
    s--;
    for (int i = 0; i < m; i++) {
        int a, b;
        fscanf(fin, "%d %d", &a, &b);
        a--;
        b--;
        v[a].push_back(b);
    }
    for (int i = 0; i < n; i++)
        dp[i] = INT_MAX;
    queue<int> q;
    q.push(s);
    dp[s] = 0;
    while (!q.empty())
    {
        int tp = q.front();
        q.pop();
        for (auto j: v[tp]) {
            if (dp[j] > dp[tp] + 1) {
                dp[j] = dp[tp] + 1;
                q.push({j});
            }
        }
    }
    for (int i = 0; i < n; i++)
        fprintf(fout, "%d ", (dp[i] == INT_MAX) ? -1 : dp[i]);
    fprintf(fout, "\n");
}