#include <bits/stdc++.h>

using namespace std;

class Graf {
private:
    int nr_noduri;
    int nr_muchii;
    vector<vector <int>> lista_vecini;

public:
    Graf();

    Graf(int nr_noduri, int nr_muchii);

    ~Graf();

    vector<vector<int>> getlista_vecini();

    void graf_neorientat(istream &fis_sursa);

    void graf_orientat(istream &fis_sursa);

    void graf_orientat_DFS(istream &fis_sursa);

    void DFS(int nod, vector<bool> &vizitat);

    int comp_conexe();

    void BFS(int nod, ostream &fis_destinatie);

    void hakimi(int noduri, vector<int> &lista, ostream &fis_destinatie);

    int DFS_sortaret(queue<int> &ordine);

    void inserare_subgraf_biconex(int x, int y, vector<vector<int>> componente_biconexe, stack<pair<int,int>> stiva);

    void DFS_biconex(int nod, int nod1, int niv, vector<int> &nivel, vector<int> &nivel_minim, stack<pair<int,int>> stiva, vector<vector<int>> &componente_biconexe);

    int disjoint_gasit(int a, vector<int> &v);

    void disjoint_uneste(int a, int b, vector<int> &v, vector<int> &rang);

    void dijkstra(vector<pair<int, int>> &muchii, vector<int> &distante, int x);

    int grupa(int grade[100005],int i);

    void reuniune(int grade[100005], int i, int j);

    void apm(int st[100005], int dr[100005], int costuri[100005], int indici[100005], vector<int> &ordine_muchii, int grade[100005], int &cost);

    void royfloyd(int a[105][105]);

    void darb(int start, int contor[100005], bool vizitat[100005], queue<int> coada, int &capat, int &diametru);

    int ciclu_hamiltonian(istream &fis_sursa, vector<int> lista[21], int matrice[263000][21], int costuri[21][21], int inf);
};
    Graf::Graf()
    {
        nr_noduri = 0;
        nr_muchii = 0;
    }

    Graf::Graf(int nr_noduri_fis, int nr_muchii_fis)
    {
        vector<int> v(1,-1);
        nr_noduri = nr_noduri_fis;
        nr_muchii = nr_muchii_fis;
        for(int i = 0; i <= nr_noduri; i++)
            lista_vecini.push_back(v);
    }
    Graf::~Graf()
    {
        nr_noduri = 0;
        nr_muchii = 0;
        lista_vecini.clear();
    }

    vector<vector<int>> Graf::getlista_vecini()
    {
        return lista_vecini;
    }

    void Graf::graf_neorientat(istream &fis_sursa)
    {
        int a, b;
        if(nr_muchii)
            for(int i = 1; i <= nr_muchii; i++)
            {
                fis_sursa >> a >> b;
                lista_vecini[a].push_back(b);
                lista_vecini[b].push_back(a);
            }
        else
            /*
            while(!fis_sursa.eof())
            {
                fis_sursa >> a >> b;
                lista_vecini[a].push_back(b);
                lista_vecini[b].push_back(a);
            }
            */

    void Graf::graf_orientat(istream &fis_sursa)
    {
        int a, b;
        for(int i = 1; i <= nr_muchii; i++)
        {
            fis_sursa >> a >> b;
            lista_vecini[a-1].push_back(b-1);
        }
    }

    void Graf::graf_orientat_DFS(istream &fis_sursa)
    {
        int a, b;
        for(int i = 1; i <= nr_muchii; i++)
        {
            fis_sursa >> a >> b;
            lista_vecini[a].push_back(b);
        }
    }

    void Graf::DFS(int nod, vector<bool> &viz)
    {
        viz[nod] = 1;
        for(int i = 1; i < lista_vecini[nod].size(); i++)
            if(viz[lista_vecini[nod][i]] == 0)
                DFS(lista_vecini[nod][i], viz);
    }

    int Graf::comp_conexe()
    {
        int nr = 0;
        vector<bool> viz(nr_noduri + 1, 0);
        for(int i = 1; i <= nr_noduri; i++)
            if(!viz[i])
            {
                nr++;
                DFS(i, viz);
            }
        return nr;
    }

    void Graf::BFS(int nod, ostream &fis_destinatie)
    {
        int a;
        queue<int> coada;
        vector<int> dist(nr_noduri, -1);
        dist[nod-1] = 0;
        coada.push(nod-1);
        while(!coada.empty())
        {
            a = coada.front();
            coada.pop();
            for(auto& i: lista_vecini[a])
                if(dist[i] == -1)
                {
                    dist[i] = dist[a] + 1;
                    coada.push(i);
                }
        }
        for(int i = 0; i < nr_noduri; i++)
            fis_destinatie << dist[i] << " ";
    }

    void Graf::hakimi(int noduri, vector<int> &lista, ostream &fis_destinatie)
    {
        int cond = 0;
        while(cond == 0)
        {
            sort(lista.begin(), lista.end(), greater<>());
            if ( lista[0] == 0)
                cond = 1;
            cout<<lista[0]<<" ";
            int aux = lista[0];
            lista.erase(lista.begin() + 0);

            if(aux > lista.size())
                cond = -1;
            for(int i = 0; i < aux; i++)
                {
                    lista[i]--;
                    if(lista[i] < 0)
                        cond = -1;
                }
        }
        if(cond == 1)
            fis_destinatie << "DA\n";
        else
            fis_destinatie << "NU\n";
    }

    int Graf::DFS_sortaret(queue<int> &lista)
    {
        queue<int> nod_grade;
        vector<int> grade_interne(100005, 0);
        for(int i = 1; i <= nr_noduri; i++)
            for(int j = 1; j < lista_vecini[i].size(); j++)
                grade_interne[lista_vecini[i][j]] += 1;
        for(int i = 1; i <= nr_noduri; i++)
            if(grade_interne[i] == 0)
                nod_grade.push(i);
        while(!nod_grade.empty())
        {
            int aux = nod_grade.front();
            nod_grade.pop();
            lista.push(aux);
            for(int i = 1; i < lista_vecini[aux].size(); i++)
            {
                grade_interne[lista_vecini[aux][i]] --;
                if(grade_interne[lista_vecini[aux][i]] == 0)
                    nod_grade.push(lista_vecini[aux][i]);
            }
        }
        if(nr_noduri == lista.size())
            return 1;
        else
            return 0;
    }

    void Graf::inserare_subgraf_biconex(int x, int y, vector<vector<int>> componente_biconexe, stack<pair<int,int>> stiva)
    {
        vector<int> subgraf;
        int a, b;
        do{
            a = stiva.top().first;
            b = stiva.top().second;
            stiva.pop();
            subgraf.push_back(a);
            subgraf.push_back(b);
        }while(a != x || b != y);
        componente_biconexe.push_back(subgraf); // adaug subgraful biconex
    }

    void Graf::DFS_biconex(int nod, int nod1, int niv, vector<int> &nivel, vector<int> &nivel_minim, stack<pair<int, int>> stiva, vector<vector<int>> &componente_biconexe)
    {
        vector<int>::iterator it;
        nivel[nod] = nivel_minim[nod] = niv; // stabilesc nivelul curent
        for(it = lista_vecini[nod].begin(); it != lista_vecini[nod].end(); ++it)
        {
            if(*it == nod1) // daca este nodul cautat, continui
                continue;
            if(nivel[*it] == -1)
            {
                stiva.push(make_pair(nod, *it)); // adaug muchia in stiva
                DFS_biconex(*it, nod, niv + 1, nivel, nivel_minim, stiva, componente_biconexe); // continui parcurgerea
                nivel_minim[nod] = min(nivel_minim[nod], nivel[*it]);
                if(nivel_minim[*it] >= nivel[nod]) // verific daca am gasit un subgraf biconex
                    inserare_subgraf_biconex(nod, *it, componente_biconexe, stiva);
            }
            else
            nivel_minim[nod] = min(nivel_minim[nod], nivel[*it]);
        }
    }

    int Graf::disjoint_gasit(int a, vector<int> &v)
    {
        int i, aux;
        for (i = a; v[i] != i; i = v[i]); // caut in arbore un nod ce pointeaza la el insusi

        for(; v[a] != a;) // realizez compresia drumurilor
        {
            aux = v[a];
            v[a] = i;
            a = aux;
        }
        return i;
    }

    void Graf::disjoint_uneste(int a, int b, vector<int> &v, vector<int> &rang)
    {
        if(rang[a] > rang[b]) // atasez multimea cu rang mai mic la cea cu rang mai mare
            v[b] = a;
        else v[a] = b;
        if(rang[a] == rang[b]) // maresc rangul multimii pe care vreau sa o adaug recent in caz de egalitate
            rang[b]++;
    }
   /* void Graf::dijkstra(vector<pair<int, int>> &muchii, vector<int> &distante, int x)
    {
        distante[1] = 0;
        set<pair<int, int>> s;
        s.insert(make_pair(0, 1)); //introduc nodul 1
        while(!s.empty()) // cat timp nu am parcurs toate nodurile la care pot ajunge
        {
            int nod = s.begin()->second;
            int d = s.begin()->first;
            s.erase(s.begin());
            for(vector<pair<int, int>>::iterator it = muchii[nod].begin(); it != muchii[nod].end(); ++it) // ma plimb in muchiile care incep cu nodul respectiv
            {
                int capat = it->first;
                int cost = it->second;
                if(distante[capat] > distante[nod] + cost) // verific daca distanta este minima
                {
                    if(distante[capat] != x)
                        s.erase(s.find(make_pair(distante[capat], capat))); // o sterg daca nu distanta nu este val initiala
                    distante[capat] = distante[nod] + cost;
                    s.insert(make_pair(distante[capat], capat)); // calculez distanta minima si o adaug in set
                }
            }
        }
    } */

    int Graf::grupa(int grade[100005],int i) // returnez gradul nodului in arbore
    {
        if(grade[i] == i) return i;
        grade[i] = grupa(grade, grade[i]);
        return grade[i];
    }

    void Graf::reuniune(int grade[100005], int i, int j) // realizez conexitatea a doua noduri pentru arborele final
    {
        grade[grupa(grade, i)] = grupa(grade, j);
    }

    void Graf::apm(int st[100005], int dr[100005], int costuri[100005], int indici[100005], vector<int> &ordine_muchii, int grade[100005], int &cost)
    {
        for(int i = 1; i <= nr_muchii; ++i)
            if(grupa(grade, st[indici[i]]) != grupa(grade, dr[indici[i]])) // daca nodurile nu fac parte din arbore deja, le adaug in arbore
            {
                cost += costuri[i];
                reuniune(grade, st[indici[i]], dr[indici[i]]); // fac gradul celor doua noduri egal
                ordine_muchii.push_back(indici[i]);
            }
    }

    void Graf::royfloyd(int a[105][105])
    {
        for(int k = 1; k <= nr_noduri; k++)
            for(int i = 1; i <= nr_noduri; i++)
                for(int j = 1; j <= nr_noduri; j++)
                    if(a[i][k] && a[k][j] && (a[i][j] > a[i][k] + a[k][j] || !a[i][j]) && i != j)
                        a[i][j] = a[i][k] + a[k][j]; // daca exista un traseu mai scurt de la un nod la altul, ii modific distanta
    }

    void Graf::darb(int start, int contor[100005], bool vizitat[100005], queue<int> coada, int &capat, int &diametru)
    {
        memset(contor, 0, 100005);
        memset(vizitat, 0, 100005);
        coada.push(start);
        contor[start] = 1;
        vizitat[start] = 1;
        int i, el;
        while(!coada.empty())
        {
            el = coada.front();
            for(i = 0; i < lista_vecini[el].size(); i++)
            {
                if(vizitat[lista_vecini[el][i]] == 0)
                {
                    coada.push(lista_vecini[el][i]);
                    contor[lista_vecini[el][i]] = contor[el] + 1;
                    vizitat[lista_vecini[el][i]] = 1;
                    diametru = contor[lista_vecini[el][i]]; // stabilesc diametrul ca fiind distanta de nodul maxim la care am ajuns
                    capat = lista_vecini[el][i]; // tin minte pentru a doua parcurgere, cea finala
                }
            }
            coada.pop();
        }
    }

    int Graf::ciclu_hamiltonian(istream &fis_sursa, vector<int> lista[21], int matrice[263000][21], int costuri[21][21], int inf)
    {
        for (int i = 0; i < nr_noduri; ++i)
		for (int j = 0; j < nr_noduri; ++j)
            costuri[i][j] = inf;

        for (int i = 1; i <= nr_muchii; ++i)
        {
            int x, y;

            fis_sursa >> x >> y;
            lista[y].push_back(x);
            fis_sursa >> costuri[x][y];
        }

        for (int i = 0; i < 1 << nr_noduri; ++i)
            for (int j = 0; j < nr_noduri; ++j)
                matrice[i][j] = inf;

        matrice[1][0] = 0;

        for (int i = 0; i < 1 << nr_noduri; ++i)
            for (int j = 0; j < nr_noduri; ++j)
                if (i & (1 << j))
                    for (int k = 0; k < lista[j].size(); ++k)
                        if (i & (1 << lista[j][k]))
                            matrice[i][j] = min(matrice[i][j], matrice[i ^ (1<<j)][ lista[j][k] ] + costuri[ lista[j][k] ][j]);

        int rezultat = inf;
        for (int i = 0; i < lista_vecini[0].size(); ++i)
            rezultat = min(rezultat, matrice[(1<<nr_noduri) - 1][ lista[0][i] ] + costuri[ lista[0][i] ][0]);
        return rezultat;
    }

void pb1_BFS()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    int N, M, S;
    f >> N >> M >> S;
    Graf graf(N, M);
    graf.graf_orientat(f);
    graf.BFS(S, g);
    f.close();
    g.close();
}

void pb2_DFS()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int N, M;
    f >> N >> M;
    Graf graf(N, M);
    graf.graf_neorientat(f);
    g << graf.comp_conexe();
    f.close();
    g.close();
}

void pb_hakimi()
{
    ifstream f("hakimi.in");
    ofstream g("hakimi.out");
    int N;
    vector<int> V(100005);
    f >> N;
    for(int i = 0; i < N; i++)
        f >> V[i];
    Graf graf(N, 0);
    graf.hakimi(N, V, g);
    f.close();
    g.close();
}

void pb_sortaret()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int N, M, x;
    vector<bool> viz(100005, 0);
    queue<int> lista;
    f >> N >> M;
    Graf graf(N, M);
    graf.graf_orientat_DFS(f);
    x = graf.DFS_sortaret(lista);
    if(x)
    {
        while(!lista.empty())
        {
            g << lista.front() <<" ";
            lista.pop();
        }
    }
    else
        g << "Graful nu are o sortare topologica!";
    f.close();
    g.close();
}

void pb_biconex()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    int N, M, nr_biconexe = 0;
    vector<int> nivel(100005, -1);
    vector<int> nivel_minim(100005);
    stack<pair<int, int>> stiva;
    vector<vector<int>> componente_biconexe;
    f >> N >> M;
    Graf graf(N, M);
    graf.graf_neorientat(f);
    graf.DFS_biconex(1, 2, 0, nivel, nivel_minim, stiva, componente_biconexe);
    g << componente_biconexe.size() << "\n";
    for(int i = 0; i < componente_biconexe.size(); i++)
    {
        sort(componente_biconexe[i].begin(), componente_biconexe[i].end());
        componente_biconexe[i].erase(unique(componente_biconexe[i].begin(), componente_biconexe[i].end()), componente_biconexe[i].end());
        for(int j = 0; j < componente_biconexe[i].size(); j++)
            g << componente_biconexe[i][j] << " ";
        g << "\n";
    }
    f.close();
    g.close();
}

void pb_disjoint()
{
    ifstream f("disjoint.in");
    ofstream g("disjoint.out");
    vector<int> v(100005);
    vector<int> rang(100005);
    int cod, a, b, N, M;
    f >> N >> M;
    Graf graf(N, 0);
    for(int i = 1; i <= N; i++)
    {
        v[i] = i;
        rang[i] = 1;
    }
    for(int i = 1; i <= M; i++)
        {
            f >> cod >> a >> b;
            if (cod == 2)
            {
                if(graf.disjoint_gasit(a, v) == graf.disjoint_gasit(b, v)) //verifica daca am aceiasi radacina
                    g << "DA\n";
                else
                    g << "NU\n";
            }
            else //unesc nodurile
            {
                graf.disjoint_uneste(graf.disjoint_gasit(a, v), graf.disjoint_gasit(b, v), v, rang);
            }
        }
}
/*
void pb_dijkstra()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    vector<pair<int, int>> muchii(100005);
    int x = 10000000;
    vector<int> distante(100005, x);
    int N, M, A, B, C;
    f >> N >> M;
    Graf graf(N,0);
    for(int i = 0; i < M; i++)
    {
        f >> A >> B >> C;
        muchii[A].push_back(make_pair(B, C));
    }
    return ;
    graf.dijkstra(muchii, distante, x);
    for(int i = 2; i <= N; i++)
    {
        if(distante[i] == x)
            distante[i] = 0;
        g << distante[i] << " ";
    }
} */

void schimbare(int* a, int* b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

int ajutor_sortare(int indici[100001], int costuri[100001], int minim, int maxim)
{
    int pivot = costuri[maxim];
    int i = minim - 1;
    for(int j = minim; j <= maxim - 1; j++)
    {
        if(costuri[j] <= pivot)
        {
            i++;
            schimbare(&costuri[i], &costuri[j]);
            schimbare(&indici[i], &indici[j]);
        }
    }
    schimbare(&costuri[i + 1], &costuri[maxim]);
    schimbare(&indici[i + 1], &indici[maxim]);
    return (i + 1);
}

void sortare_apm(int indici[100001], int costuri[100001], int minim, int maxim)
{
    if(minim < maxim)
    {
        int x = ajutor_sortare(indici, costuri, minim, maxim);
        sortare_apm(indici, costuri, minim, x - 1);
        sortare_apm(indici, costuri, x + 1, maxim);
    }
}

void pb_apm()
{
    vector<int> ordine_muchii;
    int N, M, cost = 0, cost1 = 0;
    int st[100005], dr[100005], costuri[100005], indici[100005], grade[100005];
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> N >> M;
    Graf graf(N, M);
    for(int i = 1; i <= M; ++i)
    {
        f >> st[i] >> dr[i] >> costuri[i];
        indici[i] = i;
    }
    for(int i = 1; i <= N; ++i)
        grade[i] = i;
    sortare_apm(indici, costuri, 1, M);
    graf.apm(st, dr, costuri, indici, ordine_muchii, grade, cost);
    g << cost << "\n";
    g << N-1 << "\n";
    for(int i = 0; i < N-1; ++i)
        g << st[ordine_muchii[i]] << " " << dr[ordine_muchii[i]] << "\n";
}


void pb_royfloyd()
{
    ifstream f("royfloyd.in");
    ofstream g("royfloyd.out");
    int a[105][105], n;
    f >> n;
    Graf graf(n, 0);
    for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                f >> a[i][j];
    graf.royfloyd(a);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            g << a[i][j] << " ";
        g << "\n";
    }
}

void pb_darb()
{
    ifstream f("darb.in");
    ofstream g("darb.out");
    queue<int> coada;
    int contor[100005];
    bool vizitat[100005];
    int N, nod_departat_initial , nod_departat_final , diametru;
    f >> N ;
    Graf graf(N, 0);
    graf.graf_neorientat(f);
    graf.darb(1, contor, vizitat, coada, nod_departat_initial, diametru);
    graf.darb(nod_departat_initial, contor, vizitat, coada, nod_departat_final, diametru);
    g << diametru;
}

void pb_hamiltonian()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    int N, M, inf = 100000000;
    int matrice[263000][21], costuri[21][21];
    vector<int> lista[21];
    f >> N >> M;
    Graf graf(N, M);
    int rezultat = graf.ciclu_hamiltonian(f, lista, matrice, costuri, inf);
    if (rezultat == inf)
        g << "Nu exista solutie";
    else
        g << rezultat;
}

int main() {

    pb2_DFS();
    return 0;
}