#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

list<pair<int,int>> * readEdges(int& n, int& m, int& s, ifstream & in){
    //dynamically allocate a list of pairs
    list<pair<int,int>> * E = new list<pair<int,int>>;
    //read dimentions and start node
    in>>n>>m>>s;
    int x, y;
    //read edges
    while(in>>x>>y){
        E->push_back(pair<int,int>(x,y));
    }
    //return the list
    return E;
}

vector<list<int>> * edgesToList(list<pair<int,int>> * E, int n,bool directed){
    //create a vector of lists
    vector<list<int>> * L = new vector<list<int>>;
    //set the vector's length to the number of nodes
    L->resize(n);
    //traverse the list of edges and add them to the adjacency lists
    for(auto p : *E){
        (*L)[p.first - 1].push_back(p.second);
        if(!directed){
            (*L)[p.second - 1].push_back(p.first);
        }
    }
    //return the lists
    return L;
}

void BFS(vector<list<int>> * L, int n, int start, int * length){
    bool visited [n];
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    // int * parinte = new int[n + 1];
    queue<int> q;
    int curent;

    // parinte[start] = 0;
    q.push(start);
    visited[start - 1] = true;
    length[start - 1] = 0;

    while(!q.empty()){
        //get the next node to visit
        curent = q.front();
        q.pop();
        //go through all the node's neighbours
        for(auto x : (*L)[curent - 1]){
            if(!visited[x - 1]){
                //"visit it"
                q.push(x);
                // parinte[x] = curent;
                visited[x - 1] = true;
                length[x - 1] = length[curent - 1] + 1;
            }
        }
    }

}


int main(){
    int n, m, s;
    ifstream f("graf.in");
    list<pair<int, int>> * E = readEdges(n, m, s, f);
    vector<list<int>> * L = edgesToList(E, n, true);

    int * length = new int[n];
    for(int i = 0; i < n; i++){
        length[i] = -1;
    }

    BFS(L, n, s, length);

    for(int i = 0; i < n; i++){
        cout<<length[i]<<' ';
    }

    f.close();
}