/*
ID: gabriel100
LANG: C++
TASK:
*/
#include <cstdio>
#include <algorithm>
//#include <time.h>
#include <queue>
#include <cmath>
#include <stack>
#include <fstream>
#include <bitset>
#include <set>
#include <map>
#include <ctime>
#include <list>

#define nl '\n'
#define F first
#define S second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define eb(x) emplace_back(x)
#define ull unsigned long long
#define ll long long
#define ProblemName "bfs"
#define LocalName "data"
#ifdef INFOARENA
#define Filename ProblemName
#else
#define Filename LocalName
#endif
#define Input Filename".in"
#define Output Filename".out"
using namespace std;
ifstream cin(Input);
ofstream cout(Output);

template<class a, class type>
void print(a v, type t) {
    for_each(all(v), [](type x) { cout << x << ' '; });
    cout << nl;
}

typedef struct nod {
    list<int> v;
}p;
int n, m,x,y;
p v[100001];
inline void add(int ind, int val){
    v[ind].v.push_back(val);
}
int pas[100001];
//inline void dfs(int i){
//    for(auto it = v[i].v.begin();it !=v[i].v.end();++it){
//        if(!viz[*it]){
//            dfs(*it);
//        }
//    }
//}
inline void bfs(int s){
    queue<int> q;
    q.push(s);
    int i;
    while (!q.empty()){
        i = q.front();
        q.pop();
        for(auto it = v[i].v.begin();it != v[i].v.end();++it){
            if(!pas[*it]){
                q.push(*it);
                pas[*it] = pas[i]+1;
            }
        }
    }
}
int s;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    clock_t tStart = clock();
    cin >> n >> m >> s;
    pas[s] = 1;
    for(int i=0;i<m;++i) {
        cin >> x >> y;
        add(x,y);
    }
    bfs(s);
    for(int i=1;i<=n;++i){
        cout << pas[i]-1 << ' ';
    }
    cout.close();
//    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}