#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <fstream>
 
using namespace std;
 
int main(){
 
    int vertices, edges, start;
    int x, y;
     
    ifstream f("bfs.in");
    f >> vertices >> edges >> start;
 
    vector<list<int> > adList(vertices + 1);
 
    for(int i = 0; i < edges; i++){
        f >> x >> y;
        adList[x].push_back(y);
    }
    f.close();
 
    queue<int> q;
    vector<int> visited(vertices + 1, 0);
    vector<int> costs(vertices + 1, -1);
 
    q.push(start);
    visited[start] = 1;
    costs[start] = 0;
 
    while(!q.empty()){
 
        int current = q.front();
        q.pop();
 
        list<int>::iterator i;
        for(i = adList[current].begin(); i != adList[current].end(); i++)
            if(visited[*i] == 0){
                q.push(*i);
                costs[*i] = costs[current] + 1;
                visited[*i] = 1;
            }
    }
 
    ofstream g("bfs.out");
    for(int i = 1; i < vertices + 1; i++)
        g << costs[i] << " ";
 
    return 0;
 
}