#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    ifstream in("bfs.in");
    ofstream out("bfs.out");

    int m,n,s;
    in>>n>>m>>s;

    vector<pair<vector<int>,int> > v;v.reserve(+n);
    for(int i=0;i<n+1;i++){
        v.push_back(pair<vector<int>,int>(vector<int>(),-1));
    }
    for(int i=0;i<m;i++){
        int x,y;
        in>>x>>y;
        v[x].first.push_back(y);
    }
    v[s].second=0;
    queue<int> q;q.push(s);
    while(!q.empty()){
        for(int i=0;i<v[q.front()].first.size();i++){
            if(v[v[q.front()].first[i]].second==-1 or v[v[q.front()].first[i]].second>v[q.front()].second+1){
                v[v[q.front()].first[i]].second=v[q.front()].second+1;
                q.push(v[q.front()].first[i]);
            }
        }
        q.pop();
    }
    for(int i=1;i<n+1;i++){
        out<<v[i].second<<" ";
    }
}