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

using namespace std;

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

int main(){
    int v1,v2; // noduri
    int number_of_vertices,number_of_nodes,starting_node;
    int cost = 1;
    queue<int>bfs;
    unordered_map<int,vector<int>>adj_list;
    fin>> number_of_nodes >> number_of_vertices >> starting_node;
    vector<bool>visited(number_of_nodes+1,false);
    vector<int>costs(number_of_nodes+1,-1);
    for(int i = 0; i < number_of_vertices; i++){
        fin>>v1>>v2;
        if(v1!=v2)
            adj_list[v1].push_back(v2);
    }
    
    bfs.push(starting_node);
    costs[starting_node] = 0;
    visited[starting_node] = true;
    while(!bfs.empty()){
        bool added_on_queue = false; //verifica daca am facut vreo modificare cozii
        for(auto neighbor: adj_list[bfs.front()])
        {
            if(!visited[neighbor])
            {   
                added_on_queue = true;
                costs[neighbor] = cost;
                bfs.push(neighbor);
                visited[neighbor] = true;
            }
        }
        if(added_on_queue)
            cost+=1;
        bfs.pop();
    }
    for(int i = 1; i < costs.size(); i++)
        fout << costs[i] << " ";
    return 0;
}