# include <cstdio>
# include <stdlib.h>
# include <algorithm>

/*# include "queue.h"
# include "vector.h"*/

using namespace std;

# define FIN "bfs.in"
# define FOUT "bfs.out"

     
     
     template <class T> class vector {
    
          struct lista {
                 T info;
                 lista *next, *prev;
                 
                 lista(T _info, lista *_next, lista *_prev) {
                      info = _info;
                      next = _next;
                      prev = _prev;
                 }
          } *F, *L;
          
          public:
                 vector() : F(NULL), L(NULL) { }
                 ~vector();
                 
                 vector<T> &operator=(const vector<T> &); // copy vector content
                 
                 int size() const;                        // returns size
                 bool empty() const;                      // test wether vector is empty
                 
                 T front() const;                         // access first element
                 T back() const;                          // access last element
                 T operator[](int) const;                 // access element
                 
                 void push_back(T);                       // add element at the end
                 void pop_back();                         // delete last element
                 void clear();                            // clear content
                 
                 class iterator;
                 friend class iterator;
                 class iterator {
                       
                       lista *p;
                       
                       public:
                              iterator() : p(NULL) { }
                              iterator(const iterator &It) {
                                   *this = It;
                              }
                              iterator(const vector<T> &V) {
                                   p = V.F ? new lista(V.F -> info, V.F -> next, V.F -> prev) : NULL;
                              }
                              
                              ~iterator() {
                                   delete p;
                              }
                              
                              iterator &operator++() {
                                   p = p ? p -> next : NULL;
                                   return *this;
                              }
                              
                              T operator*() const {
                                   return p -> info;
                              }
                              
                              bool operator!=(const iterator &It) const {
                                   return p != It.p;
                              }
                              
                              bool operator==(const iterator &It) const {
                                   return p == It.p;
                              }
                              
                              iterator &operator=(const iterator &It) {
                                   p = It.p ? new lista(It.p -> info, It.p -> next, It.p -> prev) : NULL;
                                   
                                   return *this;
                              }
                 } it;
                 
                 iterator begin() const {                  // return iterator to beginning
                      return iterator(*this);
                 }
                 
                 iterator end() const {                    // return iterator to end
                      return iterator();
                 }
     };
     
     template <class T> void vector<T> :: clear() {
          lista *p;
          
          while (F) {
                p = F;
                F = F -> next;
                delete p;
          }
          
          F = L = NULL;
     }
     
     template <class T> vector<T> :: ~vector() {
          clear();
     }
     
     template <class T> bool vector<T> :: empty() const {
          return !F ? true : false;
     }
     
     template <class T> int vector<T> :: size() const {
          int length = 0;
          
          for (iterator it = begin(); it != end(); ++it, ++length);
          
          return length;
     }
     
     template <class T> T vector<T> :: front() const {
          return F -> info;
     }
     
     template <class T> T vector<T> :: back() const {
          return L -> info;
     }
     
     template <class T> void vector<T> :: push_back(T value) {
          L = (!F ? F : L -> next) = new lista(value, NULL, L);
     }
     
     template <class T> void vector <T> :: pop_back() {
          if (L -> prev) {
              lista *p;
              
              p = L;
              L -> prev -> next = NULL;
              L = L -> prev;
              delete p;
              
              return;
          }
          
          delete L; F = L = NULL;
     }
     
     template <class T> T vector<T> :: operator[](int poz) const {
          iterator it;
          for (it = begin(); poz; ++it, --poz);
          
          return *it;
     }
     
     template <class T> vector<T> & vector<T> :: operator=(const vector<T> &V) {
          clear();
          
          for (iterator it = V.begin(); it != V.end(); ++it) push_back(*it);
          
          return *this;
     }


    template <class T> class queue {
         
         struct lista {
                T info;
                lista *next;
                
                lista(T _info, lista *_next) {
                     info = _info;
                     next = _next;
                }
         } *F, *L;
         
         public:
                queue();
                ~queue();
                
                int size() const;     // return size
                bool empty() const;   // test wether queue is empty
                
                T back() const;       // access last element
                T front() const;      // access first element
                
                void pop();           // delete first element
                void push(T );        // insert element at the end
    };
    
    template <class T> queue<T> :: queue() {
         F = L = NULL;
    }
    
    template <class T> queue<T> :: ~queue() {
         while (!empty()) pop();
    }
    
    template <class T> int queue<T> :: size() const {
         lista *p;
         int sz = 0;
         
         for (p = F; p; p = p -> next, ++sz);
         
         return sz;
    }
    
    template <class T> bool queue<T> :: empty() const {
         return !F;
    }
    
    template <class T> T queue<T> :: back() const {
         return L -> info;
    }
    
    template <class T> T queue<T> :: front() const {
         return F -> info;
    }
    
    template <class T> void queue<T> :: pop() {
         lista *p = F; F = F -> next; delete p;
    }
    
    template <class T> void queue<T> :: push(T value) {
         L = (F ? L -> next : F ) = new lista(value, NULL);
    }



     template <class T> class graph {
          
          int N, M;
          vector <pair<int, T> > *G;
          
          public:
                 graph(int, int);
                 ~graph();
                 
                 void set_dim(int, int);
                 void push_edge(int, int);
                 void push_edge(int, T, int);
                 
                 void bfs(int) const;
     };
     
     template <class T> graph<T> :: graph(int vertex = 0, int edge = 0) {
          set_dim(vertex, edge);
     }
     
     template <class T> graph<T> :: ~graph() {
          for (int i = 1; i <= N; ++i) G[i].clear();
          delete[] G;
          N = M = 0;
     }
     
     template <class T> void graph<T> :: set_dim(int vertex, int edge) {
          N = vertex; M = edge;
          G = new vector <pair<int, T> > [N + 1];
     }
     
     template <class T> void graph<T> :: push_edge(int src, int dest) {
         G[src].push_back(make_pair(dest, 0));
     }
     
     template <class T> void graph<T> :: push_edge(int src, T cost, int dest) {
          G[src].push_back(make_pair(dest, cost));
     }
     
     template <class T> void graph<T> :: bfs(int start_node) const {
          queue<int> Q;
          int s[N + 1];
          
          memset(s, 0, sizeof(s)); s[start_node] = 1; Q.push(start_node);
          while (!Q.empty()) {
               int Nod = Q.front();
               for (G[Nod].it = G[Nod].begin(); G[Nod].it != G[Nod].end(); ++G[Nod].it)
                   if (!s[(*G[Nod].it).first]) {
                        s[(*G[Nod].it).first] = s[Nod] + 1;
                        Q.push((*G[Nod].it).first);
                   }
               Q.pop();
          }
          
          for (int i = 1; i <= N; ++i) printf("%d ", --s[i]);
     }
     
     int main() {
          freopen(FIN, "r", stdin);
          freopen(FOUT, "w", stdout);
         
          graph<int> A;
          
          int N, M, src, dest, cost, start_node;
          
          scanf("%d%d%d", &N, &M, &start_node);
          A.set_dim(N, M);
          
          for (int i = 1; i <= M; ++i) {
              scanf("%d%d", &src, &dest);
              
              A.push_edge(src, dest);
          }

          A.bfs(start_node);
         
          return 0;
     }