#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector<int> rezultat;
vector<int> vis;
vector<int> distanta;

void bfs(vector<vector<int>> &vecini, int start) {
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    distanta[start] = 0;

    while(!q.empty()) {
        int curent = q.front();
        rezultat.push_back(curent);
        q.pop(); 
        
        for (auto vecin : vecini[curent]) {
            if (vis[vecin] == 0) {
                vis[vecin] = 1;
                distanta[vecin] = distanta[curent] + 1;
                q.push(vecin);
            }
        } 
    }

}
int main() {

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

    int n, m, start;
    fin >> n >> m >> start;
    vector<vector<int>> vecini(n+1);

    vis.assign(n+1, 0);
    distanta.assign(n+1, -1);
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        vecini[x].push_back(y);
        // vecini[y].push_back(x);
    }
    bfs(vecini, start);

    for (int i = 1; i < distanta.size(); i++) {
        fout << distanta[i] << " ";
    }
    fout << endl;

    fin.close();
    fout.close();
    
    return 0;
}