//
//  main.cpp
//  01BFS
//
//  Created by Sorin Sebastian Mircea on 31/12/2016.
//  Copyright © 2016 Sorin Sebastian Mircea. All rights reserved.
//

#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
#define MAXN 100000
#define INF 0x3f3f3f3f

vector<int> graf[MAXN];
queue<int> coada;
int d[MAXN];
int n, m, start;

int main() {
    int i, j, x, y, crt;
    cin >> n >> m >> start;
    for(i=1; i<=m; i++) {
        cin >> x >> y;
        graf[x].push_back(y);
    }
    
    for(i=1; i<=n; i++)
        d[i] = INF;
    
    d[start] = 0;
    coada.push(start);
    
    while(!coada.empty()) {
        crt = coada.front(); coada.pop();
        
        for(j=0; j < graf[crt].size(); j++) {
            if( d[ graf[crt][j] ] > d[crt] + 1 ) {
                d[ graf[crt][j] ] = d[crt] + 1;
                coada.push( graf[crt][j] );
            }
        }
    }
    
    for(i=1; i<=n; i++)
        if(d[i] == INF)
            cout << "-1 ";
        else
            cout << d[i] << " ";
    
    return 0;
        
}