#include <iostream>
#include <queue>

using namespace std;

#define INF (1 << 29)
///^^Eso es operaciones de bits. Es equivalente a hacer 1 * (2^29) -> dos elevado a la veintinueve, y todo eso multiplicado por 1.

vector <vector <int> > ady;

vector <int> BFS(int cantNodos, int nodoInicial)
{
    vector <int> dist(cantNodos+1, INF); ///Inicialmente todos tienen distancia INFINITO
    queue <int> cola;

    ///Para empezar el algoritmo tengo que asignar distancia cero al nodoInicial, y ponerlo en cola
    cola.push(nodoInicial);
    dist[nodoInicial] = 0;

    while(cola.size()) ///Eso ejecuta siempre y cuando el tamaño sea distinto que cero
    {
        int nodo = cola.front(); ///Obtengo el elemento del principio
        cola.pop(); ///Saco dicho elemento

        for(int i=0; i<ady[nodo].size(); i++)
        {
            int vecino = ady[nodo][i]; ///Nodo vecino a nodo
            if(dist[nodo] + 1 < dist[vecino]) ///Si puedo mejorar la distancia
            {
                dist[vecino] = dist[nodo] + 1; ///La mejoro
                cola.push(vecino); ///Y mando al vecino a la cola
            }
        }
    }

    return dist; ///Devuelvo el vector con las distancias mínimas.
}

int main()
{
    int N, M;
    cin >> N >> M;

    ady = vector <vector <int> > (N+1);

    for(int i=0; i<M; i++)
    {
        int desde, hasta;
        cin >> desde >> hasta;
        ady[desde].push_back(hasta);
        ady[hasta].push_back(desde);
    }

    int nodoInicial;
    cin >> nodoInicial;

    vector <int> distancias = BFS(N, nodoInicial);

    for(int i=1; i<=N; i++)
    {
        cout << "La menor distancia desde " << nodoInicial << " hasta " << i << " es : " << distancias[i] << endl;
    }

}