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

using namespace std;

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

class Graf
{
    int tip;
    int nr_noduri;
    int nr_muchii;
    vector <vector <int>> lista_vecini;

public:
    Graf() {
        tip = 0;
        nr_noduri = 0;
        nr_muchii = 0;
    }
    Graf(int tip, int nr_noduri, int nr_muchii, vector <vector<int>> lista_vecini) {
        this->tip = tip;
        this->nr_noduri = nr_noduri;
        this->nr_muchii = nr_muchii;
        this->lista_vecini.resize(nr_noduri + 1);
        for (int i = 1; i <= nr_noduri; i++)
            for (int j = 0; j < lista_vecini[i].size(); j++)
                this->lista_vecini[i].push_back(lista_vecini[i][j]);
    }
    ~Graf() { }

    friend istream& operator>>(istream& in, Graf& g);
    friend ostream& operator<<(ostream& out, const Graf& g);

    void BFS(int start) {
        //cout << "\nIntroduceti nodul de start: ";
        //int start;
        //cin >> start;

        queue <int> bfs_tree;
        vector <int> viz;
        for (int i = 0; i <= this->nr_noduri; i++)
            viz.push_back(-1);

        bfs_tree.push(start);
        viz[start] = 0;

        while (!bfs_tree.empty()) {
            int nod_curent = bfs_tree.front();
            bfs_tree.pop();

            for (int i = 0; i < lista_vecini[nod_curent].size(); i++)
                if (viz[lista_vecini[nod_curent][i]] == -1) {
                    viz[lista_vecini[nod_curent][i]] = viz[nod_curent] + 1;
                    bfs_tree.push(lista_vecini[nod_curent][i]);
                }
        }

        //cout << "\nVectorul distantelor: ";
        for (int i = 1; i <= this->nr_noduri; i++)
            out << viz[i] << " ";
    }
    void DFS(int start, vector <int> &viz) {
        stack <int> dfs_tree;

        dfs_tree.push(start);
        viz[start] = 1;

        while (!dfs_tree.empty()) {
            int nod_curent = dfs_tree.top();
            int vecin = 0;
            for (int i = 0; i < lista_vecini[nod_curent].size(); i++)
                if (viz[lista_vecini[nod_curent][i]] == 0) {
                    vecin = lista_vecini[nod_curent][i];
                    break;
                }
            if (vecin == 0)
                dfs_tree.pop();
            else {
                dfs_tree.push(vecin);
                viz[vecin] = 1;
            }
        }

    }
    void comp_conexe() {
        vector <int> viz;
        for (int i = 0; i <= this->nr_noduri; i++)
            viz.push_back(0);

        int nr_comp = 0;

        for(int i=1; i<=this->nr_noduri; i++)
            if(viz[i] == 0) {
                DFS(i, viz);
                nr_comp++;
            }

        //cout << "\nNumar de componente conexe: " << nr_comp << " ";
        out << nr_comp;
    }

};

istream& operator>>(istream& in, Graf& g)
{
    cout << "\nIntroduceti tipul grafului (0-Neorientat 1-Orientat):";
    in >> g.tip;
    if (g.tip == 0) {
        cout << "\nIntroduceti numarul de noduri: ";
        cin >> g.nr_noduri;
        cout << "\nIntroduceti numarul de muchii: ";
        cin >> g.nr_muchii;
        cout << "\nIntroduceti lista muchiilor: ";
        g.lista_vecini.resize(g.nr_noduri + 1);
        for (int i = 0; i < g.nr_muchii; i++) {
            int x, y;
            cin >> x >> y;
            g.lista_vecini[x].push_back(y);
            g.lista_vecini[y].push_back(x);
        }
    }
    else if(g.tip == 1) {
        cout << "\nIntroduceti numarul de noduri: ";
        cin >> g.nr_noduri;
        cout << "\nIntroduceti numarul de arce: ";
        cin >> g.nr_muchii;
        cout << "\nIntroduceti lista arcelor: ";
        g.lista_vecini.resize(g.nr_noduri + 1);
        for (int i = 0; i < g.nr_muchii; i++) {
            int x, y;
            cin >> x >> y;
            g.lista_vecini[x].push_back(y);
        }
    }
    else {
        cout << "\nTip gresit";
    }

    return in;
}
ostream& operator<<(ostream& out, const Graf& g)
{
    cout << "\nTip graf: ";
    if (g.tip == 0) {
        cout << "neorientat";
        cout << "\nNumar de noduri: " << g.nr_noduri;
        cout << "\nNumar de muchii: " << g.nr_muchii;
        cout << "\nLista de vecini: ";
        for (int i = 1; i <= g.nr_noduri; i++)
        {
            for (int j = 0; j < g.lista_vecini[i].size(); j++)
                cout << g.lista_vecini[i][j] << " ";
            cout << "\n";
        }
    }
    else if (g.tip == 1) {
        cout << "orientat";
        cout << "\nNumar de noduri: " << g.nr_noduri;
        cout << "\nNumar de arce: " << g.nr_muchii;
        cout << "\nLista de vecini: ";
        for (int i = 1; i <= g.nr_noduri; i++)
        {
            for (int j = 0; j < g.lista_vecini[i].size(); j++)
                cout << g.lista_vecini[i][j] << " ";
            cout << "\n";
        }
    }

    return out;
}



int main()
{
    int n,m,s;
    vector <vector<int>> v;

    in >> n >> m >> s;
    v.resize(n+1);
    for(int i=0; i<m; i++)
    {
        int x,y;
        in >> x >> y;
        v[x].push_back(y);
    }

    Graf g(1,n,m,v);
    g.BFS(s);

    in.close();
    out.close();
    return 0;
}