//
//  main.cpp
//  Algoritmi aplicati pe grafuri
//
//  Created by Mara Dascalu on 27/10/2021.
//

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <queue>

using namespace std;

//ifstream input("dfs.in");
//ofstream output("dfs.out");

ifstream input("bfs.in");
ofstream output("bfs.out");

 class Graph
{
    int nodes, edges;
    map<int, list<int>> adj;
    int cost[100010];
    queue<int> queue_bfs;
    list<int> :: iterator iter;
   
public:
    
    map<int, bool> visited;
    void set_no_nodes(int n) {nodes = n;}
    int get_no_nodes() {return nodes;}
    void set_no_edges(int n) {edges = n;}
    int get_no_edges() {return edges;}
    void addEdge (int a, int b)
    {
        adj[a].push_back(b);
//        adj[b].push_back(a);
    }
    void DFS(int node)
    {
        visited[node] = 1;
        //output<<node<<" ";
        
        for (iter = adj[node].begin(); iter != adj[node].end(); iter++)
            if( !visited[*iter])
                DFS(*iter);
    }
//    void afis_adj(int node){
//        list<int> :: iterator i;
//        for(i = adj[node].begin(); i != adj[node].end(); i++)
//            output<<*i<<" ";
//    }
    
    void BFD (int node)
    {
        memset(cost,  -1, sizeof(cost));
        visited[node] = 1; //marchez nodul curent ca vizitat
        queue_bfs.push(node);
        cost[node] = 0;
        
        while (!queue_bfs.empty()) {
            node = queue_bfs.front(); //iau nodul din varful cozii
            queue_bfs.pop();
            
            for (iter = adj[node].begin(); iter != adj[node].end(); iter++) //parcurg toti vecinii sai
                if ( !visited[*iter]) //daca sunt nevizitati
                {
                    visited[*iter] = 1;  //ii marchez ca vizitati
                    queue_bfs.push(*iter);   //ii adaug in coada
                    cost[*iter] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
                }
        }
    }
    void out_cost (int no)
    {
        for (int i = 1; i <= no; i++)
        output<<cost[i]<<" ";
    }

}g;
int main(int argc, const char * argv[]) {
    /// PROBLEMA DFS INFOARENA
//    int no_nodes, no_edges, n1, n2, cc=0;
//    input>>no_nodes>>no_edges;
//    for (int i = 0; i < no_edges; i++)
//    {
//        input>>n1>>n2;
//        g.addEdge(n1, n2);
//    }
//    for (int i = 1; i <= no_nodes; i++)
//        if (!g.visited[i])
//        {
//            cc++;
//            g.DFS(i);
//        }
//    output<<cc<<" ";
    
    ///PROBLEMA BFS INFOARENA
    
    int no_nodes, no_edges, start, n1, n2;
    input>>no_nodes>>no_edges>>start;
    
    for (int i = 0; i < no_edges ; i++)
    {
        input>>n1>>n2;
        g.addEdge(n1, n2);
    }
    
    g.BFD(start);
    g.out_cost(no_nodes);
}