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

using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
class graf
{
    int n,m,s;
    vector< vector<int> > lista_vecini;
public:
    graf(unsigned int);
    int setn(const int x);
    int setm(const int x);
    int getn();
    int getm();
    int gets();
    void getvecini();
    void BFS();
    void DFS(unsigned int);
};


graf::graf(unsigned int opt)
{
    int x,y;
    switch (opt)
    {
    case 1:
        f>>this->n>>this->m>>this->s;
        this->lista_vecini.resize(n+1);
        for (int i=0; i<m; ++i)
        {
            f>>x>>y;
            this->lista_vecini[x].push_back(y);
        }
        break;
    case 2:
        f>>this->n>>this->m;
        this->lista_vecini.resize(n+1);
        for (int i=0; i<m; ++i)
        {
            f>>x>>y;
            this->lista_vecini[x].push_back(y);
            this->lista_vecini[y].push_back(x);
        }
        break;
    default:
        break;
    }
}

int graf::getm()
{
    return this->m;
}

int graf::getn()
{
    return this->n;
}

int graf::gets()
{
    return this->s;
}

void graf::getvecini()
{
    for (unsigned int i=1; i<this->lista_vecini.size(); ++i)
    {
        cout<<i<<": ";
        for (unsigned int j=0; j<this->lista_vecini[i].size(); ++j)
            cout<<this->lista_vecini[i][j]<<" ";
        cout<<"\n";
    }
}

void graf::BFS()
{
    int d[this->n+1],rez[this->n+1];
    for (int i=1; i<=n; ++i)
        f>>rez[i];
    for (int i=1; i<=n; ++i)
        d[i]=-1;
    bool viz[this->n+1];
    for (int i=1; i<=n; ++i)
        viz[i]=false;
    unsigned int index=0;
    vector <int> coada;
    coada.push_back(this->s);
    d[this->s]=0;
    viz[this->s]=true;
    while (index<coada.size())
    {
        int nod_curent=coada[index++];
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (!viz[this->lista_vecini[nod_curent][i]])
            {
                coada.push_back(this->lista_vecini[nod_curent][i]);
                viz[this->lista_vecini[nod_curent][i]]=true;
                d[this->lista_vecini[nod_curent][i]]=d[nod_curent]+1;
            }
    }
    for (int i=1; i<=n; ++i)
    {
        if (d[i]!=rez[i])
            cout<<"eroare\n";
        g<<d[i]<<" ";
    }
}

void graf::DFS(unsigned int nod_curent)
{
    static bool *viz=new bool[this->n+1];
    static unsigned int nrconex;
    if (nod_curent==0)
    {
        for (int i=1; i<=n; ++i)
            viz[i]=false;
        nrconex=0;
        for (int i=1; i<=n; ++i)
            if (!viz[i])
            {
                nrconex++;
                DFS(i);
            }
        delete [] viz;
        g<<nrconex;
    }
    else
    {
        viz[nod_curent]=true;
        for (unsigned int i=0; i<this->lista_vecini[nod_curent].size(); ++i)
            if (!viz[lista_vecini[nod_curent][i]])
                DFS(lista_vecini[nod_curent][i]);
    }
}

int main()
{
    graf a(2);
    //a.getvecini();
    a.DFS(0);
    return 0;
}