/*
Se da un graf neorientat cu N noduri si M muchii.
sa se determine nr de componente conexa ale grafului.
Fisierul de intrare dfs.in contine pe prima linie numerele N si M cu semnificatia din enunt, iar pe urmatoarele M linii se gasesc cate doua numere X si Y cu semnificatia: exista muchie de la nodul X la nodul Y.
*/

#include<iostream>
#include<fstream>
#include<vector>


using namespace std;

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

const int NR_MAX_NODURI=100000;
vector<int>G[NR_MAX_NODURI+1];
bool vizitat[NR_MAX_NODURI+1];

void dfs(int nod_start){
    vizitat[nod_start]=true;
    for(auto urm_nod:G[nod_start]){
        if(vizitat[urm_nod]==false){
            dfs(urm_nod);
        }
    }
}

int main(){
    int N,M;
    f>>N>>M;
    int nod1,nod2;
    for(int i=1; i<=M;i++){
        f>>nod1>>nod2;
        G[nod1].push_back(nod2);
        G[nod2].push_back(nod1);
    }
    //afisam graful
    for(int i=1; i<=N; i++){
        cout<<"Nodul "<<i<<" : ";
        for(auto j:G[i]){
            cout<<j<<" ";
        }
        cout<<endl;
    }
    //parcurgem graful
    int nr_componente_conexe=0;
    for(int i=1;i<=N;i++){
        if(vizitat[i]==false){
            nr_componente_conexe++;
            dfs(i);
        }
    }
    
    cout<<"Nr de componente conexa este: "<<nr_componente_conexe;
    
    return 0;
}