#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in ("bfs.in");
ofstream out ("bfs.out");

int N, M, S;
const int Size = 100002;
vector <int> G[Size];
//G[x] = list with all nodes with an edge from x to them
bool vis[Size];
int path[Size];
queue<int> q;

int main()
{
    in >> N >> M >> S;
    int x, y, i;
    for(i = 1; i <= M; i++){
        in >> x >> y;
        G[x].push_back(y);
    }
    for(i = 1; i <= N; i++){
        vis[i] = false;
        path[i] = -1;
    }
    vis[S] = true;
    path[S] = 0;
    q.push(S);
    int node, neigh;
    while(!q.empty()){
        node = q.front();
        q.pop();
        for(i = 0; i < G[node].size(); i++){
            neigh = G[node][i];
            if(vis[neigh] == false){
                q.push(neigh);
                path[neigh] = path[node] + 1;
                vis[neigh] = true;
            }
        }
    }
    for(i = 1; i <= N; i++)
        out << path[i] << " ";
    return 0;
}