#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
ifstream in;
ofstream out;
using namespace std;

class Graph {
    unsigned int nr_muchii, nr_noduri, nod_start;
    vector<vector<pair<int, int>>> lista_vecini;
    void BFS (unsigned int, int[]);
    void DFS (unsigned int, bool[]);
public:
    Graph(string, bool);
    void problemaBFS();
    void problemaDFS();

};

Graph::Graph(string optiune, bool are_nod_start = false) {
    if (optiune == "orientat") {
        in >> this->nr_noduri >> this->nr_muchii;
        this->lista_vecini.resize(this->nr_noduri + 1);
        if (are_nod_start) {
            in >> this->nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= this->nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
//            cout << muchie_a << " " << muchie_b << endl;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
        }
    }

    if (optiune == "neorientat") {
        in >> this->nr_noduri >> this->nr_muchii;
        this->lista_vecini.resize(this->nr_noduri + 1);
        if (are_nod_start) {
            in >> this->nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
            this->lista_vecini[muchie_b].push_back(make_pair(muchie_a, 0));
        }
    }

    //    cout << endl;
//    for (int i = 0; i < this->lista_vecini.size(); i ++) {
//        cout << i << ": ";
//        for (int j = 0; j < this->lista_vecini[i].size(); j++) {
//            cout << "(" << this->lista_vecini[i][j].first << "," << this->lista_vecini[i][j].second << "), ";
//        }
//        cout << endl;
//    }
}

void Graph::BFS (unsigned int nod_start, int vizitat[]) {
    unsigned int index = 0;
    vector <int> coada;
    coada.push_back(nod_start);
    vizitat[nod_start] = 0;
    while (index < coada.size()) {
        int nod_curent = coada[index ++];
        for (unsigned int i = 0; i < this->lista_vecini[nod_curent].size(); ++i) {
            if (vizitat[this->lista_vecini[nod_curent][i].first] == -1) {
                coada.push_back(this->lista_vecini[nod_curent][i].first);
                vizitat[this->lista_vecini[nod_curent][i].first] = vizitat[nod_curent] + 1;
            }
        }
    }
};

void Graph::problemaBFS () {
    int vizitat[nr_noduri + 1];
    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        vizitat[i] = -1;
    }
    BFS(nod_start, vizitat);
    for (unsigned int i = 1; i <= nr_noduri; i++) {
        out << vizitat[i] << " ";
    }
}

void Graph::DFS (unsigned int nod_curent, bool vizitat[]) {
    vizitat[nod_curent] = true;
    for (unsigned int i = 0; i < lista_vecini[nod_curent].size(); i ++) {
        if (not vizitat[lista_vecini[nod_curent][i].first]) {
            DFS(lista_vecini[nod_curent][i].first, vizitat);
        }
    }
}

void Graph::problemaDFS () {
    bool vizitat[nr_noduri + 1];
    for (unsigned int i = 1; i <= nr_noduri; ++i) {
        vizitat[i] = false;
    }

    unsigned int nr_comp_conexe = 0;
    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        if (not vizitat[i]) {
            nr_comp_conexe++;
            DFS(i, vizitat);
        }
    }

    out << nr_comp_conexe;
}

int main() {
    string problema;
//    cin >> problema;
    if (problema == "bfs") {
        in.open ("bfs.in", fstream::in);
        out.open ("bfs.out", fstream::out);
        Graph graf("orientat", true);
        graf.problemaBFS();
    }

//    if (problema == "dfs") {
        in.open ("dfs.in", fstream::in);
        out.open ("dfs.out", fstream::out);
        Graph graf("neorientat", false);
        graf.problemaDFS();
//    }

}