#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
#include<algorithm>
#include<set>
using namespace std;

struct muchieCost {
    int x, y, cost;
    bool operator< (muchieCost other) {
        return cost < other.cost;
    }
};

struct muchieCapacitate {
    int x, y, capacitate;
};

class DisjointSet {
    int n;
    vector<int> r;
public:
    DisjointSet(int n);
    void merge(int x, int y);
    bool find(int x, int y);
private:
    int root(int x);
    void mergeRoot(int x, int y);
};

DisjointSet::DisjointSet(int n) {
    this->n = n;
    r.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        r[i] = -1;
    }
}

void DisjointSet :: merge(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx != rooty) {
        if (r[rootx] < r[rooty]) {
            mergeRoot(rootx, rooty);
        }
        else {
            mergeRoot(rooty, rootx);
        }
    }
}

bool DisjointSet::find(int x, int y) {
    return root(x) == root(y);
}

int DisjointSet::root(int x) {
    while (r[x] > 0) {
        x = r[x];
    }
    return x;
}

void DisjointSet :: mergeRoot(int x, int y) {
    r[x] += r[y];
    r[y] = x;
}


class Graf {
    int n; //Numarul de noduri
    int m; //Numarul de muchii
    int n1, n2; //Pentru grafuri bipartite - nr de noduri din fiecare parte

    vector< vector<int> > vecini;

    vector< vector< pair<int, int> > > veciniCost;

    vector<muchieCost> muchiiCost;

    vector<muchieCapacitate> muchiiCapacitate;

    vector< vector<int> > adiacenta;

 public:
    Graf(const int n);

    Graf(const int n, const int m, const vector< pair<int, int> > &muchii, const bool directed);

    Graf(const int n, const vector< vector<int> > &muchii, const bool directed);

    Graf(const int n, const int m, const vector<muchieCost> &muchii, const bool directed);

    Graf(const int n, const vector< vector<int> > &adiacenta);

    Graf(const int n, const int m, const vector<muchieCapacitate> &muchii);

    Graf(const int n1, const int n2, const int m, const vector< pair<int, int> > &muchii);

    void adaugaMuchie(const int x, const int y, const bool orientata);

    int nrComponenteConexe();

    vector<int> bfs(const int srs);

    vector<int> sortareTopologica();

    vector< vector<int> > componenteTareConexe();

    vector< vector<int> > componenteBiconexe();

    vector< vector<int> > muchiiCritice();

    int arborePartialMinim(vector< pair<int, int> > &muchiiArbore);

    vector<int> dijkstra(const int sursa);

    bool bellmanFord(const int sursa, vector<int> &distanta);

    int diametruArbore();

    vector< vector<int> > royFloyd();

    int fluxMaxim(const int sursa, const int destinatie);

    vector<int> cicluEulerian();

    int costCicluHamiltonian();

    int cuplaj(vector< pair<int, int> > &perechi);

private:
    void dfs(const int nod, vector<bool> &viz);

    void dfsSortare(const int nod, vector<int> &noduriSortate, vector<bool> &viz);

    void dfsTareConexe(const int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
                       vector< vector<int> > &componente, int &cnt, vector<bool> &viz);

    void dfsBiconexe(const int nod, const int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz);

    bool bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
                 vector<int> &tata, vector<bool> &vizitat);

    bool dfsCuplaj(const int nod, const vector<int> &distanta, vector<bool> &vizitat, vector<int> &pa, vector<int> &pb);
    vector<int> bfsCuplaj(const vector<int> &pa, const vector<int> &pb);
};

Graf :: Graf(const int n) {
    vecini.resize(n + 1);
    this->n = n;
    this->m = 0;
}

Graf :: Graf(const int n, const int m, const vector< pair<int, int> > &muchii, const bool directed) {
    this->n = n;
    this->m = m;
    vecini.resize(n + 1);
    for (int i = 0; i < muchii.size(); i++) {
        vecini[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            vecini[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}

Graf :: Graf(const int n, const vector< vector<int> > &muchii, const bool directed) {
    this->n = n;
    this->m = muchii.size();
    vecini.resize(n + 1);
    for (int i = 0; i < muchii.size(); i++) {
        vecini[ muchii[i][0] ].push_back(muchii[i][1]);
        if (!directed) {
            vecini[ muchii[i][1] ].push_back(muchii[i][0]);
        }
    }
}

Graf :: Graf(const int n, const int m, const vector<muchieCost> &muchii, const bool directed) {
    this->n = n;
    this->m = m;
    veciniCost.resize(n + 1);
    for (int i = 0; i < muchii.size(); i++) {
        veciniCost[ muchii[i].x ].push_back(make_pair(muchii[i].y, muchii[i].cost));
        if (!directed) {
            veciniCost[ muchii[i].y ].push_back(make_pair(muchii[i].x, muchii[i].cost));
            muchiiCost.push_back(muchii[i]);
        }
    }
}

Graf :: Graf(const int n, const int m, const vector<muchieCapacitate> &muchii) {
    this->n = n;
    this->m = m;
    vecini.resize(n + 1);
    for (int i = 0; i < muchii.size(); i++) {
        muchiiCapacitate.push_back(muchii[i]);
        vecini[ muchii[i].x ].push_back(muchii[i].y);
        vecini[ muchii[i].y ].push_back(muchii[i].x);
    }
}

Graf :: Graf (const int n, const vector< vector<int> > &adiacenta) {
    this->n = n;
    this->adiacenta.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        this->adiacenta[i].resize(n + 1);
        for (int j = 1; j <= n; j++) {
            this->adiacenta[i][j] = adiacenta[i][j];
        }
    }
}

Graf :: Graf(const int n1, const int n2, const int m, const vector< pair<int, int> > &muchii) {
    this->n1 = n1;
    this->n2 = n2;
    this->n = n1 + n2;
    this->m = m;
    vecini.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        vecini[ muchii[i].first ].push_back(muchii[i].second);
    }
}

void Graf :: adaugaMuchie(const int x, const int y, const bool orientata) {
    vecini[x].push_back(y);
    if (!orientata) {
        vecini[y].push_back(x);
    }
}

int Graf :: nrComponenteConexe() {
    vector<bool> vizitat(n + 1);
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!vizitat[i]) {
            nr++;
            dfs(i, vizitat);
        }
    }
    return nr;
}
void Graf :: dfs(const int nod, vector<bool> &vizitat) {
    vizitat[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        if (!vizitat[ vecini[nod][i] ]) {
            dfs(vecini[nod][i], vizitat);
        }
    }
}
vector<int> Graf :: bfs(const int srs) {
    vector<int> distanta(n + 1);
    for (int i = 1; i <= n; i++) {
        distanta[i] = -1;
    }
    queue<int> q;
    q.push(srs);
    distanta[srs] = 0;

    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < vecini[nod].size(); i++) {
            int vecin = vecini[nod][i];
            if (distanta[vecin] == -1) {
                distanta[vecin] = distanta[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
    return distanta;
}

vector<int> Graf :: sortareTopologica() {
    vector<int> noduriSortate;
    vector<bool> vizitat(n + 1);

    for (int i = 1; i <= n; i++) {
        if (!vizitat[i]) {
            dfsSortare(i, noduriSortate, vizitat);
        }
    }
    for (int i = 0; i < n / 2; i++) {
        swap(noduriSortate[i], noduriSortate[n - i - 1]);
    }
    return noduriSortate;
}

void Graf :: dfsSortare(const int nod, vector<int> &noduriSortate, vector<bool> &vizitat) {
    vizitat[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!vizitat[vecin]) {
            dfsSortare(vecin, noduriSortate, vizitat);
        }
    }
    noduriSortate.push_back(nod);
}

vector< vector<int> > Graf :: componenteTareConexe() {
    vector<int> level(n + 1), low(n + 1);
    vector<bool> inStack(n + 1), viz(n + 1);
    int cnt = 0;
    vector< vector<int> > componente;
    stack<int> s;

    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsTareConexe(i, level, low, s, inStack, componente, cnt, viz);
        }
    }
    return componente;
}

void Graf :: dfsTareConexe(const int nod, vector<int> &level, vector<int> &low, stack<int> &s,
                vector<bool> &inStack, vector< vector<int> > &componente, int &cnt, vector<bool> &vizitat) {

    vizitat[nod] = true;
    cnt++;
    level[nod] = low[nod] = cnt;
    s.push(nod);
    inStack[nod] = true;

    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!vizitat[vecin]) {
            dfsTareConexe(vecin, level, low, s, inStack, componente, cnt, vizitat);
        }
        if (inStack[vecin]) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }

    if (low[nod] == level[nod]) {
        vector<int> noduriComponenta;
        int nodComponenta;
        do {
            nodComponenta = s.top();
            inStack[nodComponenta] = 0;
            s.pop();
            noduriComponenta.push_back(nodComponenta);
        } while (nodComponenta != nod);
        componente.push_back(noduriComponenta);
    }
}

vector< vector<int> > Graf :: componenteBiconexe() {
    vector<int> level(n + 1), low(n + 1);
    vector<bool> vizitat(n + 1);
    vector< vector<int> > componente;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, vizitat);
    return componente;
}

vector< vector<int> > Graf :: muchiiCritice() {
    vector<int> level(n + 1), low(n + 1);
    vector<bool>  vizitat(n + 1);
    vector< vector<int> > componente, critice;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, vizitat);

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vecini[i].size(); j++) {
            if (low[ vecini[i][j] ] > level[i]) {
                vector<int> muchie;
                muchie.push_back(i);
                muchie.push_back(vecini[i][j]);
                critice.push_back(muchie);
            }
        }
    }
    return critice;
}

void Graf:: dfsBiconexe(const int nod, const int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &vizitat) {

    vizitat[nod] = 1;
    level[nod] = low[nod] = level[tata] + 1;
    s.push(nod);

    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (vecin == tata) {
            continue;
        }
        if (vizitat[vecin] == 1) {
            low[nod] = min(low[nod], level[vecin]);
            continue;
        }
        dfsBiconexe(vecin, nod, level, low, s, componente, vizitat);
        low[nod] = min(low[nod], low[vecin]);

        if (low[vecin] >= level[nod]) {
            vector<int> componenta;
            componenta.push_back(nod);
            int nodComponenta;
            do{
                nodComponenta = s.top();
                componenta.push_back(nodComponenta);
                s.pop();
            } while (nodComponenta != vecin);
            componente.push_back(componenta);
        }
    }
}

int Graf :: arborePartialMinim(vector< pair<int, int> > &muchiiArbore) {
    sort(muchiiCost.begin(), muchiiCost.end());
    int suma = 0;
    DisjointSet *disjointSet = new DisjointSet(n);

    for (int i = 0; i < muchiiCost.size(); i++) {
        if (!disjointSet->find(muchiiCost[i].x, muchiiCost[i].y)) {
            disjointSet->merge(muchiiCost[i].x, muchiiCost[i].y);
            suma += muchiiCost[i].cost;
            muchiiArbore.push_back(make_pair(muchiiCost[i].x, muchiiCost[i].y));
        }
    }
    return suma;
}

vector<int> Graf :: dijkstra(const int sursa) {
    vector<int> distanta(n + 1);
    vector<bool> vizitat(n + 1);
    set< pair<int, int> > h;
    const int inf = 2000000000;
    for (int i = 1; i <= n; i++) {
        distanta[i] = inf;
        if (i == sursa) {
            distanta[i] = 0;
        }
        h.insert(make_pair(distanta[i], i));
    }

    while (!h.empty() && h.begin()->first != inf) {
        int nod = h.begin()->second;
        h.erase(h.begin());
        vizitat[nod] = true;
        for (int i = 0; i < veciniCost[nod].size(); i++) {
            int vecin = veciniCost[nod][i].first;
            if (!vizitat[vecin] && distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
                h.erase(make_pair(distanta[vecin], vecin));
                distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
                h.insert(make_pair(distanta[vecin], vecin));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (distanta[i] == inf) {
            distanta[i] = 0;
        }
    }
    return distanta;
}

bool Graf :: bellmanFord(const int sursa, vector<int> &distanta) {
    vector<int> nrVizitat(n + 1);
    queue<int> coada;
    vector<bool> inCoada(n + 1);
    distanta.resize(n + 1);
    const int inf = 2000000000;
    for (int i = 1; i <= n; i++) {
        distanta[i] = inf;
    }
    distanta[sursa] = 0;
    inCoada[sursa] = true;
    coada.push(sursa);

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        inCoada[nod] = false;
        nrVizitat[nod] ++;
        if (nrVizitat[nod] == n) {
            return true;
        }

        for (int i = 0; i < veciniCost[nod].size(); i++) {
            int vecin = veciniCost[nod][i].first;
            if (distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
                distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
                if (!inCoada[vecin]) {
                    inCoada[vecin] = true;
                    coada.push(vecin);
                }
            }
        }
    }
    return false;
}

int Graf :: diametruArbore() {
    vector<int> distanta = bfs(1);
    int nodDepartat = 1;
    for (int i = 2; i <= n; i++) {
        if (distanta[i] > distanta[nodDepartat]) {
            nodDepartat = i;
        }
    }
    distanta = bfs(nodDepartat);
    int diametru = 0;
    for (int i = 1; i <= n; i++) {
        diametru = max(diametru, distanta[i]);
    }
    return diametru + 1;
}

vector< vector<int> > Graf :: royFloyd() {
    vector< vector<int> > distanta(n + 1);
    for (int i = 1; i <= n; i++) {
        distanta[i].resize(n + 1);
        for (int j = 1; j <= n; j++) {
            distanta[i][j] = adiacenta[i][j];
        }
    }

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i != k && j != k && i != j && distanta[i][k] != 0 && distanta[k][j] != 0 &&
                   (distanta[i][k] + distanta[k][j] < distanta[i][j] || distanta[i][j] == 0)){
                    distanta[i][j] = distanta[i][k] + distanta[k][j];
                }
            }
        }
    }
    return distanta;
}

bool Graf :: bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
             vector<int> &tata, vector<bool> &vizitat) {
    queue<int> coada;
    vizitat.resize(n + 1);
    tata.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        vizitat[i] = false;
    }
    vizitat[sursa] = true;
    coada.push(sursa);
    tata[sursa] = 0;

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        for(int i = 0; i < vecini[nod].size(); i++){
            int vecin = vecini[nod][i];
            if(!vizitat[vecin] && flux[nod][vecin] < capacitate[nod][vecin]){
                vizitat[vecin] = true;
                coada.push(vecin);
                tata[vecin] = nod;
            }
        }
    }
    return vizitat[destinatie];
}

int Graf :: fluxMaxim(const int sursa, const int destinatie) {
    vector< vector<int> > flux(n + 1), capacitate(n + 1);
    vector<int> tata;
    vector<bool> vizitat;
    int total = 0;
    for (int i = 1; i <= n; i++) {
        flux[i].resize(n + 1);
        capacitate[i].resize(n + 1);
    }
    for (int i = 0; i < muchiiCapacitate.size(); i++) {
        capacitate[ muchiiCapacitate[i].x ][ muchiiCapacitate[i].y ] = muchiiCapacitate[i].capacitate;
    }

    while(bfsFlux(sursa, destinatie, flux, capacitate, tata, vizitat)){
        for(int i = 0; i < vecini[destinatie].size(); i++){
            int vecin = vecini[destinatie][i];
            if(vizitat[vecin] && capacitate[vecin][n] > flux[vecin][n]){
                int minim = capacitate[ vecin ][destinatie] - flux[ vecin ][destinatie];
                int p = vecin;
                while(tata[p] > 0){
                    minim = min(minim, capacitate[ tata[p] ][ p ] - flux[ tata[p] ][ p ]);
                    p = tata[p];
                }

                total += minim;
                flux[vecin][destinatie] += minim;
                flux[destinatie][vecin] -= minim;
                p = vecin;
                while(tata[p] > 0){
                    flux[ tata[p] ][p] += minim;
                    flux[ p][ tata[p] ] -= minim;
                    p = tata[p];
                }
            }
        }
    }
    return total;
}

vector<int> Graf :: cicluEulerian() {
    vector< vector<pair<int, int>> > veciniMuchie(n + 1);
    vector<bool> muchieAdaugata(m + 1);
    vector<int> ciclu;
    stack<int> stiva;
    int indiceMuchie = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vecini[i].size(); j++) {
            if (vecini[i][j] >= i) {
                indiceMuchie++;
                int vecin = vecini[i][j];
                veciniMuchie[i].push_back(make_pair(vecin, indiceMuchie));
                veciniMuchie[vecin].push_back(make_pair(i, indiceMuchie));
                if (vecini[i][j] == i) {
                    j++;
                }
            }
        }
    }

    int nod;
    for (int i = 1; i <= n; i++) {
        if (vecini[i].size() != 0) {
            nod = i;
            if (vecini[i].size() % 2 == 1) {
                ciclu.push_back(-1);
                return ciclu; // Nu se poate obtine ciclu eulerian, se va returna un vector cu un singur element -1
            }
        }
    }
    stiva.push(nod);

    while (!stiva.empty()) {
        nod = stiva.top();
        int i = veciniMuchie[nod].size() - 1;
        while (i >= 0 && muchieAdaugata[ veciniMuchie[nod][i].second ]) {
            veciniMuchie[nod].pop_back();
            i--;
        }
        if (veciniMuchie[nod].size() == 0) {
            ciclu.push_back(nod);
            stiva.pop();
        }
        else {
            muchieAdaugata[ veciniMuchie[nod][i].second ] = true;
            stiva.push(veciniMuchie[nod][i].first);
            veciniMuchie[nod].pop_back();
        }
    }

    ciclu.pop_back();
    if (ciclu.size() != m) {
        ciclu.clear();
        ciclu.push_back(-1);
    }
    return ciclu;
}

int Graf :: costCicluHamiltonian() {
    vector< vector<int> > dp(1 << n);
    const int inf = 1000000000;
    for (int i = 0; i < (1 << n); i++) {
        dp[i].resize(n);
        for (int j = 0; j < n; j++) {
            dp[i][j] = inf;
        }
    }
    dp[1][0] = 0;

    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ( ( (i >> j) & 1) == 1 ) {
                for (int k = 0; k < veciniCost[j + 1].size(); k++) {
                    int vecin = veciniCost[j + 1][k].first - 1;
                    if ( ( (i >> vecin) & 1) == 0) {
                        dp[i + (1 << vecin)][vecin] = min(dp[i + (1 << vecin)][vecin],
                                                      dp[i][j] + veciniCost[j + 1][k].second);
                    }
                }
            }
        }
    }

    int sol = inf;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < veciniCost[i].size(); j++) {
            if (veciniCost[i][j].first == 1) {
                sol = min(sol, dp[(1 << n) - 1][i - 1] + veciniCost[i][j].second);
            }
        }
    }
    if (sol == inf) {
        sol = -1; //Nu exista solutie
    }
    return sol;
}

vector<int> Graf :: bfsCuplaj(const vector<int> &pa, const vector<int> &pb) {
    vector<int> distanta(n1 + 1);
    queue<int> coada;
    for (int i = 1; i <= n1; i++) {
        if (pa[i] == 0) {
            coada.push(i);
        }
        else {
            distanta[i] = -1;
        }
    }

    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        for (int i = 0; i < vecini[nod].size(); i++) {
            int vecin = vecini[nod][i];
            if (pb[vecin] != 0 && distanta[ pb[vecin] ] == -1) {
                distanta[ pb[vecin] ] = 1 + distanta[nod];
                coada.push(pb[vecin]);
            }
        }
    }
    return distanta;
}

bool Graf :: dfsCuplaj(const int nod, const vector<int> & distanta, vector<bool> &vizitat,
                       vector<int> &pa, vector<int> &pb) {
    if (vizitat[nod]) {
        return false;
    }
    vizitat[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (pb[vecin] == 0) {
            pa[nod] = vecin;
            pb[vecin] = nod;
            return true;
        }

        if (distanta[nod] == distanta[ pb[vecin] ] - 1 && dfsCuplaj(pb[vecin], distanta, vizitat, pa, pb) ) {
            pa[nod] = vecin;
            pb[vecin] = nod;
            return true;
        }
    }
    return false;
}

int Graf :: cuplaj(vector< pair<int, int> > &perechi) {
    vector<int> pa(n1 + 1), pb(n2 + 1), distanta(n1 + 1);
    vector<bool> vizitat(n1 + 1);
    int ok;

    do {
        ok = 0;
        for (int i = 1; i <= n1; i++) {
            vizitat[i] = false;
        }
        distanta = bfsCuplaj(pa, pb);
        for (int i = 1; i <= n1; i++) {
            if (pa[i] == 0 && dfsCuplaj(i, distanta, vizitat, pa, pb)) {
                ok = 1;
            }
        }
    }while (ok == 1);

    for (int i = 1; i <= n1; i++) {
        if (pa[i] != 0) {
            perechi.push_back(make_pair(i, pa[i]));
        }
    }
    return perechi.size();
}

bool havelHakimi(int n, vector<int> grade) {
    int i, ii, k;
    vector<int> frecventa, frecventaNoua;
    frecventa.resize(n);
    frecventaNoua.resize(n);
    for (i = 1; i <= n; i++) {
        if (grade[i] < 0 || grade[i] >= n) {
            return false;
        }
        frecventa[ grade[i] ]++;
    }

    for (ii = 1; ii <= n; ii++) {
        for (i = n - 1; i >= 1; i--) {
            if (frecventa[i] > 0) {
                k = i;
                break;
            }
        }
        if (i == 0) {
            return true;
        }

        frecventa[k]--;
        for (; i >= 1; i--) {
            if (frecventa[i] < k) {
                k -= frecventa[i];
                frecventaNoua[i - 1] = frecventa[i];
            }
            else {
                frecventaNoua[i - 1] = k;
                frecventaNoua[i] += frecventa[i] - k;
                k = 0;
                break;
            }
        }

        for (i = i - 1; i >= 0; i--) {
            frecventaNoua[i] += frecventa[i];
        }
        if (k > 0) {
            return false;
        }
        for (i = 0; i < n; i++) {
            frecventa[i] = frecventaNoua[i];
            frecventaNoua[i] = 0;
        }
    }
}

int main() {
    int n, m;
    vector< pair<int, int> > muchii;
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin>> n >> m;
    for (int i = 0; i < m; i++) {
        pair<int, int> muchie;
        fin>> muchie.first >> muchie.second;
        muchii.push_back(muchie);
    }
    Graf *graf = new Graf(n, m, muchii, false);
    fout<< graf->nrComponenteConexe();
    return 0;
}