#include <iostream>
#include <fstream>
#include <vector>
#define MAX 100001

using namespace std;

int n,m,s,x,y,r[MAX],pa;
vector<int> nd[MAX],p[MAX];
bool acc[MAX];

int main()
{
    ifstream f ("bfs.in");
    ofstream g ("bfs.out");
    f>>n>>m>>s;
    for(int i=1;i<=m;i++) f>>x>>y,nd[x].push_back(y);
    p[0].push_back(s);acc[s]=true;
    while(not p[pa].empty()){
      for(auto i:p[pa]){
        for(auto j:nd[i]){
          if(not acc[j]){
            p[pa+1].push_back(j);
            r[j]=pa+1; acc[j]=true;
          }
        }
      }
      pa++;
    }
    for(int i=1;i<=n;i++){
      if(r[i]!=0||i==s)g<<r[i]<<" ";
      else g<<-1<<" ";
    }
    f.close ();
    g.close ();
    return 0;
}