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

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

vector<vector<int>> list;
vector<int> nod1, nod2;
vector<int> viz, dist;
int n, m, s;



int main() {
    fin>>n>>m>>s;
    list.resize(n+1);
    nod1.resize(m);
    nod2.resize(m);

    for(int i=0; i<m; i++){
        fin>>nod1[i]>>nod2[i];
        list[nod1[i]].push_back(nod2[i]);
    }

    viz.resize(n+1);
    for(auto it = viz.begin(); it != viz.end(); it++)
        *it = 0;
    dist.resize(n+1);
    for(auto it = dist.begin(); it != dist.end(); it++)
        *it = -1;

    queue<int> q;
    q.push(s);
    viz[s] = 1;
    dist[s] = 0;
    while(!q.empty()){
        int nodcurent = q.front();
        q.pop();
        for(auto vecin:list[nodcurent])
            if(viz[vecin] == 0){
                q.push(vecin);
                dist[vecin] = dist[nodcurent] + 1;
                viz[vecin] = 1;
            }
    }
//    for(int i=1; i<=n; i++) {
//        for(auto elem:list[i])
//            cout<<elem<<" ";
//        cout << endl;
//    }
    for(auto x=dist.begin()+1; x!=dist.end(); x++)
        fout<<*x<<" ";
    fin.close();
    fout.close();
    return 0;
}