#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#define MAX 100002

using namespace std;

int main()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    vector<int> lista[MAX];
    char visited[MAX];
    int distance[MAX];
    memset(visited,0,sizeof visited);
    memset(distance, -1, sizeof distance);
    int n,m,s;
    f>>n>>m>>s;

    for(int i=0;i<m;i++){
        int a,b;
        f>>a>>b;
        lista[a].push_back(b);
    }

    distance[s]=0;
    visited[s]=1;

    queue<int> bfsq;
    bfsq.push(s);

    while(!bfsq.empty()){
        int u = bfsq.front();
        bfsq.pop();

        for(int v: lista[u]){
            if(!visited[v]){
                visited[v]=1;
                distance[v]=distance[u]+1;
                bfsq.push(v);
            }
        }
    }

    for(int i=1;i <= n;i++){
        g<<distance[i]<<" ";
    }

    return 0;
}