#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include "bits/stdc++.h"

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define F first
#define S second
#define pb emplace_back 
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
//#define debug(x) cerr << "\033[0;33m" << __LINE__ << ' ' << #x << ':' << (x) << "\n\033[0m"
#define FOR(i,a,b) for (int i=a; i<b; ++i)
#define F0R(i,a) for (int i=0; i<a; ++i)
#define FORd(i,b,a) for (int i = b-1; i >= a; --i)
#define F0Rd(i,a) for (int i = a-1; i >= 0; --i)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int MOD = 1e9 + 7;
const int mxN = 1e5 + 1;
const int INF = 1e9 + 5;
const char nl = '\n';


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

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, s;
    fin >> n >> m >> s;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }
    vector<int> distance(n + 1, -1);
    vector<bool> been(n + 1);
    queue<int> Q;
    Q.push(s);
    distance[s] = 0;
    been[s] = true;

    while(!Q.empty()) {
        int nod = Q.back();
        Q.pop();
        for (int u : adj[nod]) {
            if(been[u]) continue;
            Q.push(u);
            been[u] = true;
            distance[u] = distance[nod] + 1;
        }
    }

    for (int i = 1; i <= n; ++i) {
        fout << distance[i] << ' ';
    }
    fout << nl;
    return 0;
}