#include <iostream>
#include <fstream>

#define max 100001;
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

class Graf {
    int nrNoduri, nrMuchii;
    int matriceAdiacenta[100][100], vizitat[100001], vizitat2[100001], coada[100001];
    int pozitiePlecare, pozitieUltima;
//    int **matriceAdiacenta;
public:
    Graf();

    void BFS(int nodPlecare);

    void DFS(int nodPlecare);

    void citire2(int &nodPlecare);

    void BFS2(int nodPlecare);

    void afisareCoada2();

    void citire();

    void afisare();

    void afisareCoada();

    ~Graf();
};

// neorientat
Graf::Graf() {
//    matriceAdiacenta = new int *[nrNoduri];  /// tabloul pointerilor de linii
//    for (int i = 0; i < nrNoduri; i++)
//        matriceAdiacenta[i] = new int[nrNoduri]; /// tabloul valorilor din linie
    for (int i = 1; i <= max i++)
        vizitat[i] = 0, vizitat2[i] = -1;
    pozitiePlecare = pozitieUltima = 1;
//    coada[1] = 2;
//    vizitat[2] = 1;
}

Graf::~Graf() {
//    for (int i = 0; i < nrNoduri; i++)
//        delete[] matriceAdiacenta[i];
//    delete[] matriceAdiacenta;
}

void Graf::DFS(int nodPlecare) {
    vizitat[nodPlecare] = 1; // marchez nodul de plecare ca fiind vizitat
    fout << nodPlecare << " ";
    for (int j = 1; j <= nrNoduri; j++)
        if (matriceAdiacenta[nodPlecare][j] == 1 && vizitat[j] == 0)
            // daca exista muchie de la nodul de plecare la nodul curent si nu este vizitat apelez recursiv
            DFS(j);
}

void Graf::BFS(int pozitiePlecare) {
    int nodPlecare = coada[pozitiePlecare]; // retin nodul de unde plec
    for (int j = 1; j <= nrNoduri; j++)
        if (matriceAdiacenta[j][nodPlecare] == 1 && vizitat[j] == 0) {
            // caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
            vizitat[j] = 1; // il marcam vizitat
            pozitieUltima++; // indexez pozitia ultimului element din coada
            coada[pozitieUltima] = j; // il adaug in coada PUSH
        }
    if (pozitiePlecare < pozitieUltima) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
        BFS(pozitiePlecare + 1);
    // 5 4 3 2 1
    // 0 1 2 3 4
    // pozitiePlecare = 1
    // 4 3 2 1
}

void Graf::afisareCoada() {
    for (int i = 1; i <= pozitieUltima; i++)
        cout << coada[i] << " ";
}

void Graf::citire() {
    int x, y;
    fin >> nrNoduri >> nrMuchii;
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> x >> y;
        matriceAdiacenta[x][y] = matriceAdiacenta[y][x] = 1;
    }
    fin >> coada[1];
    vizitat[coada[1]] = 1;
}

void Graf::afisare() {
    fout << '\n';
    for (int i = 1; i <= nrNoduri; i++) {
        for (int j = 1; j <= nrNoduri; j++)
            fout << matriceAdiacenta[i][j] << " ";
        fout << '\n';
    }
}

void Graf::citire2(int &nodPlecare) {
    int x, y;
    fin >> nrNoduri >> nrMuchii >> nodPlecare;
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> x >> y;
        matriceAdiacenta[x][y] = 1;
    }
    coada[1] = nodPlecare;
    vizitat2[coada[1]] = 1;
}

void Graf::BFS2(int pozitiePlecare) {
    int nodPlecare = coada[pozitiePlecare]; // retin nodul de unde plec
    for (int j = 1; j <= nrNoduri; j++)
        if (matriceAdiacenta[nodPlecare][j] == 1 && vizitat2[j] == -1) {
            // caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
            vizitat2[j] = vizitat2[nodPlecare] + 1; // il marcam vizitat
            pozitieUltima++; // indexez pozitia ultimului element din coada
            coada[pozitieUltima] = j; // il adaug in coada PUSH
        }
    if (pozitiePlecare < pozitieUltima) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
        BFS2(pozitiePlecare + 1);
}

void Graf::afisareCoada2() {
    for (int i = 1; i <= nrNoduri; i++) {
        if (vizitat2[i] != -1)
            fout << vizitat2[i] - 1 << " ";
        else
            fout << -1 << " ";
    }
}

int main() {

    int nodPlecare;
    Graf g1;
//    g1.citire();
//    g1.DFS(2);
//    g1.BFS(1);
//    g1.afisareCoada();
//    g1.afisare();
    g1.citire2(nodPlecare);
    g1.BFS2(1);
    g1.afisareCoada2();
    return 0;
}