#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;
vector<int> ad[MAXN];
ifstream fin ("bfs.in");
ofstream fout("bfs.out");
int coada[MAXN], d[MAXN];
int n, m, s, x, y, nod, i, prim, ultim;
int main(){
    fin>>n>>m>>s;
    for (int i=1;i<=m;i++){
        fin>>x>>y;
        ad[x].push_back(y);
    }
    prim=1;
    ultim=1;
    coada[1]=s;
    d[s]=1;
    while(prim<=ultim){
        nod=coada[prim];
        for(i=0;i<ad[nod].size();i++){
            int vecin=ad[nod][i];
            if(d[vecin]==0){
                ultim++;
                coada[ultim]=vecin;
                d[vecin]=d[nod]+1;
            }
        }

        prim++;
    }
    for(int i=1;i<=n;i++)
        fout<<d[i]<<" ";

}