#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define SIZE 100100
#define FIN "bfs.in"
#define FOUT "bfs.out"

typedef unsigned int uint;

using namespace std;
vector<uint> Graph[SIZE];
uint visited[SIZE];
queue<uint> q;
uint nodes, edges;
int costs[SIZE];
int s;

void addEdge(int x, int y) {

     Graph[x].push_back(y);
}

void read() {

     int x, y;
     ifstream fin(FIN);

     fin>>nodes>>edges>>s;

     while(edges--) {

     	   fin>>x>>y;

     	   addEdge(x,y);
     }
}

void bfs(uint node) {

     //cout<<node<<" ";

     for(vector<uint>::iterator it = Graph[node].begin(); it != Graph[node].end(); it++) {

         if(!visited[*it]) {

     	     visited[*it] = 1;

     	     costs[*it] = costs[node] + 1;

     	     q.push(*it);
     	  }   
     }
      
     q.pop();

     if(!q.empty()) bfs(q.front());     
}

void displayGraph() {

	 for(uint i = 1; i <= nodes; ++i) {

           if(Graph[i].size() > 0)

              for(vector<uint>::iterator it = Graph[i].begin(); it != Graph[i].end(); it++) {

              	  cout<<*it<<" ";    
              }

              cout<<endl;
	 }
}
void displayCosts() {
	 ofstream fout(FOUT);
	 for(int i = 1; i <= nodes; ++i) fout<<costs[i]<<" ";
}	
int main(int argc, char const *argv[])
{

    read();
   // displayGraph();
    
    for(int i = 1; i <= nodes; ++i) costs[i] = -1;
    //for(int i = 1; i <= nodes; ++i) {

       //if(!visited[i]) 
         costs[s] = 0;   
         visited[s] = 1,

         q.push(s),

         bfs(s);
    //}   
    displayCosts(); 
    return 0;
}