#include<fstream>
#define Max 80001

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int n,m,s;
long a[Max][Max/20],b[Max],c[Max],pus[Max];
void read(){
     int x,y;
     fin>>n>>m>>s;
     for(int i = 1; i <= m; i++)
     {
             fin>>x>>y;
             a[x][0]++;
             a[x][a[x][0]] = y;
     }
fin.close();
}

void bf(){
     int i,st,dr;
     st = 1;
     dr = 1;
   while(st <= dr){
           for(i = 1; i <= a[b[st]][0]; i++)
                      if(!pus[a[b[st]][i]])
                      {
                                        dr++;
                                        b[dr] = a[b[st]][i];
                                        pus[a[b[st]][i]] = 1;
                                        c[a[b[st]][i]] = c[b[st]]+1;
                      }
           st++;
   }
}
int main(){
    read();
    pus[s] = 1;
    b[1] = s;
    bf();
for(int i = 1; i <= n; i++)
if(pus[i] == 0)
c[i] = -1;
for(int i = 1; i <= n; i++)
fout<<c[i]<<" ";
fout.close();
return 0;
}