#include <bits/stdc++.h>

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

int n, m, s;
std::vector < std::vector <int> > graf(100001);
int costuri[100001];
bool viz[100001];
std::queue < int > bfs;
int cc = 0;

int main() {
    fin>>n>>m>>s;

    for(int i = 0; i < m; i++) {
        int node1, node2;
        fin>>node1>>node2;
        graf[node1].push_back(node2);
    }

    bfs.push(s);

    while(!bfs.empty()) {
        int curent = bfs.front();
        bfs.pop();

        for(int i = 0; i < graf[curent].size(); i++) {
            if(!viz[graf[curent][i]]) {
                bfs.push(graf[curent][i]);
                costuri[graf[curent][i]] = cc + 1;
                viz[graf[curent][i]] = true;
            } else if(costuri[graf[curent][i]] > cc + 1) {
                bfs.push(graf[curent][i]);
                costuri[graf[curent][i]] = cc + 1;
            }
        }
        cc++;
    }
    
    for(int i = 1; i <= n; i ++) {
        fout<<costuri[i]<<" ";
    }

    return 0;
}