#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>struct list_elem
{
public:
    T info;
    list_elem<T> *next;
    list_elem<T> *prev;
};

template <typename T>class LinkedList
{
    list_elem<T> *pFirst, *pLast;
    int size;
public:
    LinkedList()
    {
        pFirst=NULL;
        pLast=NULL;
        size = 0;
    }

   ~LinkedList()
    {

    }

    void addLast(T info)
    {
        struct list_elem<T> *p;
        p=new struct list_elem<T>;
        p->info=info;
        p->prev=pLast;
        p->next=NULL;
        if(pLast!=NULL)
            pLast->next=p;
        pLast=p;
        if(pFirst==NULL)
            pFirst=pLast;
        size++;
    }

    T getLast()
    {
        if(pFirst)
            return pFirst->info;
        else
            return NULL;
    }

    void removeFirst()
    {
        struct list_elem<T> *p;
        if(pFirst==NULL)
            std::cout<<"Lista goala\n";
        else
        {
            p=pFirst->next;
            if(pLast==pFirst)
                pLast=NULL;
//				delete pFirst;
            pFirst=p;
            if(pFirst!=NULL)
                pFirst->prev=NULL;
        }
        size--;
    }

    int  isEmpty()
    {
        if(pFirst!=NULL)
            return 0;
        else
            return 1;
    }

    void printList()
    {
        struct list_elem<T> *p;
        p=pFirst;
        while(p!=NULL)
        {
            std::cout<<p->info<<" ";
            p=p->next;
        }
        std::cout<<"\n";
    }

    int getSize()
    {
        if(pFirst)
            return size;
        else
            return 0;
    }

};

template <typename T>class Que
{
    LinkedList<T> *list;
public:
    Que()
    {
        list = new LinkedList<T>();
    }

    void enqueue(T info)
    {
        list->addLast(info);
    }

    T peek()
    {
        return list->getLast();
    }

    void dequeue()
    {
        list->removeFirst();
    }

    int sizeQue()
    {
        return list->getSize();
    }

    void printQ()
    {
        list->printList();
    }
};

int n,m,sursa;
 
vector < vector <int> >graph;
vector<int>visited;
 
void BFS(int vertex)
{
  if((vertex<0)||(vertex>n-1))
  {
    return;
  }
  Que <int> q;
  int element;
  q.enqueue(vertex);
  visited[vertex]=0;
 
  while(q.sizeQue () != 0)
  {
    element=q.peek();
    for(unsigned int i=0;i<graph[element].size(); i++)
    {
      if(visited[graph[element][i]]==-1)
      {
        q.enqueue(graph[element][i]);
        visited[graph[element][i]]=visited[element]+1;
      }
    }
    q.dequeue();
  }
 
}
 
 
 
int main()
{
int x,y;
  ifstream in("bfs.in");
  ofstream out("bfs.out");
  in>>n>>m>>sursa;
  sursa--;
  graph.resize(n);
  visited.resize(n,-1);
 
  for(int i=0; i<m; i++)
 
  {
    in>>x>>y;
    x=x-1;
    y=y-1;
    graph[x].push_back(y);
  }
 
 
  BFS(sursa);
  for(int j=0; j<n; j++)
  {
    out<<visited[j]<<" ";
  }
  return 0;
 
}