//
//  main.cpp
//  BFS
//
//  Created by Mara Dascalu on 03/11/2021.
//

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

using namespace std;

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

class Graph
{
    int nodes, edges;
    vector<int> adj[100010] ;
    bool visited[100010] = {0};
    int cc = 0;
    int cost[1001] = {0};
    queue<int> queue_bfs;
    int level[100010] = {0};
    int low_level[100010] = {0};
    stack<pair<int, int>> component_node;
    vector<int> vec_scc[100010];
    queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
    int indegree[100010] ; //vectorul care retine gradul interior al fiecarui nod
    vector<int> degree_seq; //vectorul care contine gradele unui posibil graf

public:

    vector<int> bcc[100010]; //vectorul care stocheaza componentele biconexe
    int current = 0;

   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_dg (int no_nodes, int no_edges)
   {
    
       set_no_nodes(no_nodes);

       int node1, node2;

       for(int i = 0 ; i < no_edges; i++)
       {
           input>>node1>>node2;
           adj[node1].push_back(node2);
       }


   }

   void addEdge_ug ()
   {
       int no_nodes, no_edges;
       input>>no_nodes>>no_edges;
       set_no_nodes(no_nodes);

       int node1, node2;

       for(int i = 0 ; i < no_edges; i++)
       {
           input>>node1>>node2;
           adj[node1].push_back(node2);
           adj[node2].push_back(node1);
       }
   }
    
    //   void afis_adj(int node){
    //       for (int i = 0; i < adj[node].size(); i++)
    //            cout<<adj[node][i]<<" ";
    //   }


   void DFS(int node)
   {
       visited[node] = 1;
//       output<<node<<" ";

       for (int i = 0; i < adj[node].size(); i++)
           if( !visited[adj[node][i]])
               DFS(adj[node][i]);
   }
    
    int connectedComponents ()
    {
        for (int i = 1; i <= get_no_nodes(); i++)
            if (!visited[i])
            {
                cc++;
                DFS(i);
            }
        return cc;
    }
    
    void BFS (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 (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
                if ( !visited[adj[node][i]]) //daca sunt nevizitati
                {
                    visited[adj[node][i]] = 1;  //ii marchez ca vizitati
                    queue_bfs.push(adj[node][i]);   //ii adaug in coada
                    cost[adj[node][i]] = 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[]) {

    int no_nodes, no_edges, start;
    input>>no_nodes>>no_edges>>start;
    
    g.addEdge_dg(no_nodes, no_edges);
    g.BFS(start);
    g.out_cost(g.get_no_nodes());
//
////    g.afis_adj(2);
}