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

using namespace std;

class Graf {
    int nrNoduri;
    vector<vector<int>> matriceAdiacenta;
    bool esteOrientat;

public:
    // Constructor cu toti parametrii
    Graf(int nrNoduri, const vector<vector<int>> &matriceAdiacenta, bool esteOrientat) {
        this->nrNoduri = nrNoduri;
        this->matriceAdiacenta = matriceAdiacenta;
        this->esteOrientat = esteOrientat;
    }

    // Constructor fara matrice de adiacenta. Pe fiecare linie a matricei punem un vector cu o singura valoare(-1)
    Graf(int nrNoduri, bool esteOrientat) {
        this->nrNoduri = nrNoduri;
        this->esteOrientat = esteOrientat;

        vector<int> v(1, -1);
        for (int i = 0; i <= nrNoduri; ++i) {
            matriceAdiacenta.push_back(v);
        }
    }

    // Citeste o pereche x,y si adauga in matricea de adiacenta muchiile/arcele citite
    void citireGraf(istream &in, int nrMuchii) {
        int x, y;
        for (int i = 0; i < nrMuchii; i++) {
            in >> x >> y;
            matriceAdiacenta[x].push_back(y);
            if (!esteOrientat) {
                matriceAdiacenta[y].push_back(x);
            }
        }
    }

    // Calculeaza distanta minima de la fiecare nod la start si o afiseaza
    void distantaMinimaBFS(ostream &out, int start) {
        // Vector pentru distanta in care fiecare element este initial -1
        vector<int> distanta(nrNoduri + 1, -1);
        distanta[start] = 0;

        // Queue in care salvam elementele care trebuiesc vizitate. Cand se goleste, nu mai avem nimic de vizitat
        queue<int> queue;
        queue.push(start);

        while (!queue.empty()) {
            start = queue.front();
            queue.pop();
            for (auto it: matriceAdiacenta[start]) {
                // Daca nu a fost vizitat inca
                if (distanta[it] == -1) {
                    distanta[it] = distanta[start] + 1;
                    queue.push(it); // Il adaugam in coada pentru a fi vizitat
                }
            }
        }

        // Afisam distanta
        for (int i = 1; i <= nrNoduri; i++) {
            out << distanta[i] << " ";
        }
    }

    void DFS(int nod, map<int, bool> &vizitate) {
        vizitate[nod] = true;
        for (int i = 1; i < matriceAdiacenta[nod].size(); i++) {
            if (vizitate.find(matriceAdiacenta[nod][i]) == vizitate.end()) {
                DFS(matriceAdiacenta[nod][i], vizitate);
            }
        }
    }

    int componenteConexeRecursiv(map<int,bool> vizitate, int startPos = 1){
        if(startPos==nrNoduri+1){
            return 0;
        } else {
            if(vizitate.find(startPos) == vizitate.end()){ // i nu exista in map => nu a fost vizitat
                DFS(startPos, vizitate);
                return 1+componenteConexeRecursiv(vizitate,startPos+1);
            } else {
                return componenteConexeRecursiv(vizitate,startPos+1);
            }
        }
    }

    int componenteConexe() {
        int ct = 0;
        map<int, bool> vizitate;
        for (int i = 1; i <= nrNoduri; i++) {
            if (vizitate.find(i) == vizitate.end()) { // i nu exista in map => nu a fost vizitat
                ct++;
                DFS(i, vizitate);
            }
        }
        return ct;
    }
};

void infoarena_bfs() {
    ifstream f("bfs.in");
    ofstream g("bfs.out");

    int N, M, S;
    f >> N >> M >> S;
    Graf graf(N, true);
    graf.citireGraf(f, M);
    graf.distantaMinimaBFS(g, S);
}

void infoarena_dfs() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    int N, M, S;
    f >> N >> M;
    Graf graf(N, false);
    graf.citireGraf(f, M);
//    map<int,bool> vizitate;
    g << graf.componenteConexe();
}

int main() {
//    infoarena_bfs();
    infoarena_dfs();
    return 0;
}