#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

///Clasa pentru reprezentare de grafuri
class Graf
{
protected:
    int nrNoduri;
    int nrMuchii;
public:
    Graf(const int nrNoduriDat, const int nrMuchiiDat);
    Graf(const Graf &grafDat);
    ~Graf();

    int getNrNoduri();
    int getNrMuchii();

    static int findDis(int elem, vector<pair<int, int>> &multimi);
    static void unionDis(const int x, const int y, vector<pair<int, int>> &multimi);
    static vector<bool> Disjoint (ifstream &in);
};
Graf :: Graf(const int nrNoduriDat, const int nrMuchiiDat)  //constructor parametrizat - nu avem lista de adiacenta
{
    nrNoduri = nrNoduriDat;
    nrMuchii = nrMuchiiDat;
}

Graf :: Graf(const Graf & grafDat)   //constructor copiere
{
    nrNoduri = grafDat.nrNoduri;
    nrMuchii = grafDat.nrMuchii;
}

Graf :: ~Graf()
{
}

int Graf :: getNrNoduri()    //getter numar noduri
{
    return nrNoduri;
}

int Graf :: getNrMuchii()    //getter numar muchii
{
    return nrMuchii;
}

int Graf :: findDis(int elem, vector<pair<int, int>> &multimi)
{
    int radacina = elem;
    while(multimi[radacina].first != radacina) {
        radacina= multimi[radacina].first;
    }
    while(multimi[elem].first != radacina) {
        int auxiliar = multimi[elem].first;
        multimi[elem].first = radacina;
        elem = auxiliar;
    }
    return radacina;
}

void Graf :: unionDis(const int x, const int y, vector<pair<int, int>> &multimi)
{
    int radX = findDis(x, multimi), radY = findDis(y, multimi);

    if(multimi[radX].second > multimi[radY].second) {
        multimi[radX].second = multimi[radX].second + multimi[radY].second;
        multimi[radY].first = radX;
        multimi[radY].second = multimi[radX].second;
    }
    else{
        multimi[radY].second = multimi[radY].second + multimi[radX].second;
        multimi[radX].first = radY;
        multimi[radX].second = multimi[radY].second;
    }
}

vector<bool> Graf :: Disjoint (ifstream &in)
{
    int N, M;
    in >> N >> M;
    vector<bool> rez;
    vector<pair<int, int>> multimi(N + 1, {0,0}); //indexare de la 1
    for(int i = 1; i <= N; ++i)
        multimi[i].first = i, multimi[i].second = 1;
    for(int i = 1; i <= M; ++i) {
        int x, y, task;
        in >> task >> x >> y;

        if (task == 1) {
            if(findDis(x, multimi) != findDis(y, multimi)) {
                unionDis(x, y, multimi);
            }
        }
        else{
            if(findDis(x, multimi) == findDis(y, multimi))
                rez.push_back(1);
            else
               rez.push_back(0);
        }
    }
    return rez;

}


class GrafFaraCost : public Graf
{
using Graf::Graf;
private:
    vector<vector<int>> lisAdiacenta;

    void DFS(const int nodStart, vector<bool> &vizitat, stack<int> &stiva);
    void ctcDFS(int x, vector<int> &disc, vector<int> &low, stack<int> &stiva, vector<bool> &gasitStiva, vector<vector<int>> &rez);
    void critConDFS(int x, vector<bool> &viz, vector<int> &disc, vector<int> &low, vector<int> &tata, vector<vector<int>> &rez);
    void biconexeDFS(int x, int tata, vector<int> &disc, vector<int> &low, stack<int> &comp, string &rez, int &nrCompBiconexe, vector<bool> &viz);
public:
    GrafFaraCost(const int nrNoduriDat, const int nrMuchiiDat);
    GrafFaraCost(const int nrNoduriDat, const int nrMuchiiDat, const vector<vector<int>> &listaData);
    GrafFaraCost(const GrafFaraCost &grafDat);//constructor copiere
    ~GrafFaraCost();


    GrafFaraCost& operator= (const GrafFaraCost &grafDat);
    friend std::ostream& operator<<(std::ostream &out, const GrafFaraCost &grafDat);

    void citireOrientatFC(istream &in);
    void citireNeorientatFC(istream &in);

    vector<int> BFS(const int nodStart);
    int nrCompConexe();
    stack<int> sortareTopologica();
    static string existaGraf(vector<int> &grade);
    vector<vector<int>> CTC();
    vector<vector<int>> CriticalConnections();
    pair<int, string> Biconex();
};
///CONSTRUCTORI
GrafFaraCost :: GrafFaraCost(const int nrNoduriDat, const int nrMuchiiDat)  : Graf(nrNoduriDat, nrMuchiiDat)
{
    vector<int> aux(1,-1);       //initializam prima pozitie cu -1 pentru ca indexarea e de la 1
    for(int i = 0; i <= nrNoduri+1; ++i) {
        lisAdiacenta.push_back(aux);
    }
}
GrafFaraCost :: GrafFaraCost(const int nrNoduriDat, const int nrMuchiiDat, const vector<vector<int>> &listaData)  : Graf(nrNoduriDat, nrMuchiiDat)
{
    lisAdiacenta = listaData;
}

GrafFaraCost :: GrafFaraCost(const GrafFaraCost & grafDat) : Graf(grafDat) //constructor copiere
{
    lisAdiacenta = grafDat.lisAdiacenta;
}

///DESTRUCTOR
GrafFaraCost :: ~GrafFaraCost()
{
    lisAdiacenta.clear();
}


///SUPRAINCARCARI OPERATORI
GrafFaraCost& GrafFaraCost :: operator= (const GrafFaraCost &grafDat)//supraincarcare operator egal
{
    if(this != &grafDat) {
        this->nrNoduri = grafDat.nrNoduri;
        this->nrMuchii = grafDat.nrMuchii;

        if(!this->lisAdiacenta.empty())
            lisAdiacenta.clear();

        this->lisAdiacenta = grafDat.lisAdiacenta;
    }

    return *this;
}

ostream& operator<< (std::ostream& out, const GrafFaraCost& grafDat)  //supraincarcare operator afisare
{
    out << "Numarul de noduri ale grafului este: " << grafDat.nrNoduri << "\n";
    out << "Numarul de muchii ale grafului este: " << grafDat.nrMuchii << "\n";

    for (int i = 1; i <= grafDat.nrNoduri; ++i) {
        out << i << ": ";
        for (int j = 1; j < grafDat.lisAdiacenta[i].size(); ++j) {
            out << grafDat.lisAdiacenta[i][j]<<" ";
        }
        out<<"\n";
    }

    return out;
}

///METODE CITIRI

void GrafFaraCost :: citireNeorientatFC(istream &in)  //citim de la tastatura sau din fisier un graf neorientat
{
    int x, y;

    for(int i = 1; i <= nrMuchii; ++i) {
        in >> x >> y;
        lisAdiacenta[x].push_back(y), lisAdiacenta[y].push_back(x);
    }
}


void GrafFaraCost :: citireOrientatFC(istream &in)   //citim de la tastatura sau din fisier un graf orientat
{
    int x, y;

    for(int i = 1; i <= nrMuchii; ++i) {
        in >> x >> y;
        lisAdiacenta[x].push_back(y);
    }
}

///Afisare distante BFS
vector<int> GrafFaraCost :: BFS(const int nodStart)     //parcurgere in latime
{
    queue<int> Q;
    int x, y;
    vector<int> distanta(nrNoduri+1, -1);

    distanta[nodStart] = 0;
    Q.push(nodStart);

    while(!Q.empty()) {
        x = Q.front();   //eliminam nodul curent din coada
        Q.pop();

        for (int i = 1; i < lisAdiacenta[x].size(); ++i)
            if (distanta[lisAdiacenta[x][i]] == -1) {              //daca nu a fost vizitat vecinul
                distanta[lisAdiacenta[x][i]] = distanta[x] + 1;    //inseamna ca am gasit drum mai scurt
                Q.push(lisAdiacenta[x][i]);
            }
    }

    return distanta;
}


///Aflare nr componente conexe
void GrafFaraCost :: DFS(const int x, vector<bool> &vizitat, stack<int> &stiva)   //parcurgere in adancime
{
    vizitat[x] = 1;

    for(int i = 1; i < lisAdiacenta[x].size(); i++)
        if(vizitat[lisAdiacenta[x][i]] == 0)    //daca vecinul sau nu a fost vizitat, mergem la el
            DFS(lisAdiacenta[x][i], vizitat, stiva);
    stiva.push(x);
}

int GrafFaraCost :: nrCompConexe()   //numar de componente conexe facut cu DFS
{
    stack<int> stiva;       //implementata formal, pentru a putea utiliza DFS ul si la sortareTopologica()
    int nrCompCon = 0;
    vector<bool> vizitat(nrNoduri+1, 0);

    for(int i = 1; i <= nrNoduri; ++i )
        if(!vizitat[i]) {
            nrCompCon++;
            DFS(i, vizitat, stiva);
        }

    return nrCompCon;
}

///Afisare sortare topologica
stack<int> GrafFaraCost :: sortareTopologica()  //afisam o sortare topologica posibila
{
    stack<int> stiva;
    vector<bool> vizitat(nrNoduri+1, 0);

    for(int i = 1; i <= nrNoduri; ++i )
        if(!vizitat[i])
            DFS(i, vizitat, stiva);

    return stiva;

}


///algoritmul Havel-Hakimi pt a afla daca o secventa de numere poate forma graf simplu
//https://www.geeksforgeeks.org/find-if-a-degree-sequence-can-form-a-simple-graph-havel-hakimi-algorithm/
//O(n^2)
string GrafFaraCost :: existaGraf(vector<int> &grade)
{
    vector<int> copieGrade;
    copieGrade = grade;

    int S = 0;      //suma grade
    for (int i = 0; i < copieGrade.size(); ++i)
        S += copieGrade[i];
    if (S % 2 == 1) {    //suma gradelor intr-un graf neorientat e mereu para
        return "Nu\n";
    }

    sort(grade.begin(), grade.end(), greater<int>());  //luam gradele in ordine descrescatoare
    while (true) {

        if (grade[0] == 0) {
                return "Da";
        }

        int fst = grade[0];
        grade.erase(grade.begin() + 0);
        if (fst > grade.size()) {  //daca avem un grad mai mare decat numarul de noduri ramase
            return "Nu";
        }

        for (int i = 0; i < fst; ++i) {
            grade[i]--;
            if (grade[i] < 0) {
                return "Nu";
            }
        }

        int j = fst;                            //reordonam descrescator
        for (int i = 0; i < fst; ++i)   {       //fiind deja ordonate descrescator
            if(j >= grade.size())               //atunci cand scadem 1 valorile nu vor mai fi ordonate decat daca sunt egale initial
                break;                           //si fst e mai mic decat numarul de valori egale intial
            if (grade[i] < grade[j]) {
                swap(grade[i], grade[j]);
                j++;
            }
        }
    }

}

///Componente Tare Conexe - Algoritmul lui Tarjan
//https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
void GrafFaraCost::ctcDFS(int x, vector<int> &disc, vector<int> &low, stack<int> &stiva, vector<bool> &gasitStiva, vector<vector<int>> &rez)
{
    static int timp = 0;

    disc[x] = low[x] = ++timp;
    stiva.push(x);
    gasitStiva[x] = 1;


    for (int i = 1; i < lisAdiacenta[x].size(); i++) {
        if (disc[lisAdiacenta[x][i]] == -1)    {
            ctcDFS(lisAdiacenta[x][i], disc, low, stiva, gasitStiva, rez);
            low[x] = min(low[x], low[lisAdiacenta[x][i]]);   //conexiune a fiului cu un stramos al lui x
        } else if (gasitStiva[lisAdiacenta[x][i]] == 1)
            low[x] = min(low[x], disc[lisAdiacenta[x][i]]);  //muchie de intoarcere
    }

    vector<int> compNoua;
    if (low[x] == disc[x]) {       //daca am gasit nod de start pt componenta tare conexa scoatem nodurile din stiva
        while (stiva.top() != x) {
            compNoua.push_back(stiva.top());
            gasitStiva[stiva.top()] = 0;
            stiva.pop();
        }

        compNoua.push_back(stiva.top());
        gasitStiva[stiva.top()] = 0;
        rez.push_back(compNoua);
        stiva.pop();
    }
}

vector<vector<int>> GrafFaraCost :: CTC()
{
    vector<int> disc(nrNoduri+1, -1);
    vector<int> low(nrNoduri+1, -1);
    stack<int> stiva;
    vector<bool> gasitStiva(nrNoduri+1, 0);
    vector<vector<int>> rez;

    for (int i = 1; i <= nrNoduri; ++i) {
        if (disc[i] == -1)
            ctcDFS(i, disc, low, stiva, gasitStiva, rez);
    }

    return rez;
}

///Muchii Critice
//https://www.geeksforgeeks.org/bridge-in-a-graph/
void GrafFaraCost::critConDFS(int x, vector<bool> &viz, vector<int> &disc, vector<int> &low, vector<int> &tata, vector<vector<int>> &rez)
{
    static int timp = 0;

    viz[x] = 1;
    disc[x] = low[x] = ++timp;

    for (int i = 1; i < lisAdiacenta[x].size(); ++i) {
        if (!viz[lisAdiacenta[x][i]])    {
            tata[lisAdiacenta[x][i]] = x;
            critConDFS(lisAdiacenta[x][i], viz, disc, low, tata, rez);
            low[x] = min(low[x], low[lisAdiacenta[x][i]]);    //conexiune a fiului cu un stramos al lui x

            if (low[lisAdiacenta[x][i]] > disc[x]) {           //daca nu putem ajunge in fiu altfel (are timpul minim mai mare decat timpul de desc)
                vector<int> aux;
                aux.push_back(x);
                aux.push_back(lisAdiacenta[x][i]);
                rez.push_back(aux);
            }
        } else if (lisAdiacenta[x][i] != tata[x])  //daca e vizitat deja si nu e parinte, modificam valoarea lui low[x]
            low[x] = min(low[x], disc[lisAdiacenta[x][i]]);
    }
}

vector<vector<int>> GrafFaraCost :: CriticalConnections()
{
    vector<bool> viz(nrNoduri+1, 0);
    vector<int> disc(nrNoduri+1);
    vector<int> low(nrNoduri+1);
    vector<int> tata(nrNoduri+1, -1);
    vector<vector<int>> rez;

    for (int i = 1; i <= nrNoduri; ++i) {
        if (!viz[i])
            critConDFS(i, viz, disc, low, tata, rez);
    }
    return rez;
}


///Biconex
//https://www.geeksforgeeks.org/biconnected-components/
void GrafFaraCost :: biconexeDFS(int x, int tata, vector<int> &disc, vector<int> &low, stack<int> &comp, string &rez, int &nrCompBiconexe, vector<bool> &viz)
{
    viz[x] = 1;
    disc[x] = disc[tata] + 1;
    low[x] = disc[x];

    for (int i = 1; i < lisAdiacenta[x].size(); ++i)
        if (lisAdiacenta[x][i] != tata) {
            if (!viz[lisAdiacenta[x][i]]) {
                comp.push(lisAdiacenta[x][i]);
                biconexeDFS(lisAdiacenta[x][i], x, disc, low, comp, rez, nrCompBiconexe, viz);

                low[x] = min(low[x], low[lisAdiacenta[x][i]]);   //conexiune a fiului cu un stramos al lui x
                if (disc[x] <= low[lisAdiacenta[x][i]]) {   //am gasit o muchie critica
                    nrCompBiconexe++;
                    comp.push(x);
                    while (!comp.empty() && comp.top() != lisAdiacenta[x][i]) {
                        rez += (to_string(comp.top()) + " ");
                        comp.pop();
                    }
                    if (!comp.empty()) {
                        rez += (to_string(comp.top()) + " ");
                        comp.pop();
                    }
                    rez += "\n";
                }
            } else if (disc[lisAdiacenta[x][i]] < low[x]) //daca e vizitat si are timpul de disc mai mic, atunci modificam timp min x
                low[x] = disc[lisAdiacenta[x][i]];
        }
}

pair<int, string> GrafFaraCost :: Biconex()
{
    vector<int> disc(nrNoduri+1, -1);
    vector<int> low(nrNoduri+1, -1);
    vector<bool> viz(nrNoduri + 1, 0);
    stack<int> comp;
    string rez = "";

    int nrCompBiconexe = 0;

    disc[1] = 1;
    biconexeDFS(2, 1, disc, low, comp, rez, nrCompBiconexe, viz);

    return make_pair(nrCompBiconexe, rez);
}


class GrafCuCost : public Graf
{
using Graf::Graf;
private:
    vector<vector<pair<int,int>>> lisAdiacenta;
    vector<pair<int, pair<int, int>>> lisMuchii;
public:
    GrafCuCost(const int nrNoduriDat, const int nrMuchiiDat);
    GrafCuCost(const int nrNoduriDat, const int nrMuchiiDat, const vector<vector<pair<int, int>>> &listaData);
    GrafCuCost(const GrafCuCost &grafDat);//constructor copiere
    ~GrafCuCost();

    vector<pair<int, pair<int, int>>> getLisMuchii();

    GrafCuCost& operator= (const GrafCuCost &grafDat);
    friend std::ostream& operator<<(std::ostream &out, const GrafCuCost &grafDat);

    void citireOrientatCC(istream &in);
    void citireNeorientatCC(istream &in);

    pair<int, vector<pair<int, int>>> Kruskal(vector<pair<int, pair<int, int>>> muchii);
    vector<int> BellmanFord(const int start);
    vector<int> Dijkstra(const int start);
};

///CONSTRUCTORI
GrafCuCost :: GrafCuCost(const int nrNoduriDat, const int nrMuchiiDat)  : Graf(nrNoduriDat, nrMuchiiDat)
{
    vector<pair<int, pair<int, int>>> auxM(1);
    lisMuchii = auxM;
    vector<pair<int, int>> aux(1,{-1, -1});       //initializam prima pozitie cu -1 pentru ca indexarea e de la 1
    for(int i = 0; i <= nrNoduri+1; ++i) {
        lisAdiacenta.push_back(aux);
    }
}
GrafCuCost :: GrafCuCost(const int nrNoduriDat, const int nrMuchiiDat, const vector<vector<pair<int,int>>> &listaData)  : Graf(nrNoduriDat, nrMuchiiDat)
{
    lisAdiacenta = listaData;
}

GrafCuCost :: GrafCuCost(const GrafCuCost & grafDat) : Graf(grafDat) //constructor copiere
{
    lisAdiacenta = grafDat.lisAdiacenta;
}

///DESTRUCTOR
GrafCuCost :: ~GrafCuCost()
{
    lisAdiacenta.clear();
    lisMuchii.clear();
}

vector<pair<int, pair<int, int>>> GrafCuCost :: getLisMuchii()
{
    return lisMuchii;
}

///SUPRAINCARCARI OPERATORI
GrafCuCost& GrafCuCost :: operator= (const GrafCuCost &grafDat)//supraincarcare operator egal
{
    if(this != &grafDat) {
        this->nrNoduri = grafDat.nrNoduri;
        this->nrMuchii = grafDat.nrMuchii;

        if(!this->lisAdiacenta.empty())
            lisAdiacenta.clear();

        this->lisAdiacenta = grafDat.lisAdiacenta;
    }

    return *this;
}

ostream& operator<< (std::ostream& out, const GrafCuCost& grafDat)  //supraincarcare operator afisare
{
    out << "Numarul de noduri ale grafului este: " << grafDat.nrNoduri << "\n";
    out << "Numarul de muchii ale grafului este: " << grafDat.nrMuchii << "\n";

    for (int i = 1; i <= grafDat.nrNoduri; ++i) {
        out << i << ": ";
        for (int j = 1; j < grafDat.lisAdiacenta[i].size(); ++j) {
            out << " (" << grafDat.lisAdiacenta[i][j].first << ", " << grafDat.lisAdiacenta[i][j].second << ") ";
        }
        out<<"\n";
    }

    return out;
}

///METODE CITIRI

void GrafCuCost :: citireNeorientatCC(istream &in)  //citim de la tastatura sau din fisier un graf neorientat
{
    int x, y, c;

    for(int i = 1; i <= nrMuchii; ++i) {
        in >> x >> y >> c;
        lisAdiacenta[x].push_back({y, c}), lisAdiacenta[y].push_back({x, c});
        lisMuchii.push_back({c, {x, y}});
    }
}



void GrafCuCost :: citireOrientatCC(istream &in)   //citim de la tastatura sau din fisier un graf orientat
{
    int x, y, c;

    for(int i = 1; i <= nrMuchii; ++i) {
        in >> x >> y >> c;
        lisAdiacenta[x].push_back({y, c});
        lisMuchii.push_back({c, {x, y}});
    }
}

pair<int, vector<pair<int, int>>> GrafCuCost :: Kruskal(vector<pair<int, pair<int, int>>> muchii)
{
    int N = nrNoduri, M = nrMuchii;
    vector<pair<int, int>> multimi(N + 1, {0, 0});
    vector<pair<int,int>> rezMuchii(1, {-1, -1});
    int costTotal = 0;

    for(int i = 1; i <= N; ++i) {
        multimi[i] = {i, 1};
    }

    sort(muchii.begin() + 1, muchii.end());

    for(int i = 1; i <= M && rezMuchii.size() < N; ++i) {
        if( findDis(muchii[i].second.first, multimi) != findDis(muchii[i].second.second, multimi) ){
            unionDis(muchii[i].second.first, muchii[i].second.second, multimi);
            costTotal = costTotal + muchii[i].first;
            rezMuchii.push_back({muchii[i].second.first, muchii[i].second.second});
        }
    }

    return {costTotal, rezMuchii};

}

vector<int> GrafCuCost :: BellmanFord(const int start)
{
    vector<int> distBMF(nrNoduri + 1, INF);
    vector<int> viz(nrNoduri + 1, 0);
    vector<bool> apartCoada(nrNoduri + 1, false);
    queue<int> coada;
    int faraCiclNeg = 1;

    coada.push(start), apartCoada[start] = 1;
    distBMF[start] = 0;

    while (!coada.empty() && faraCiclNeg) {
        int x = coada.front();
        coada.pop();
        apartCoada[x] = 0;

        for (int i = 1; i < lisAdiacenta[x].size(); i++)
                if (distBMF[x] + lisAdiacenta[x][i].second < distBMF[lisAdiacenta[x][i].first]) {
                    distBMF[lisAdiacenta[x][i].first] = distBMF[x] + lisAdiacenta[x][i].second;      //relaxam
                    viz[lisAdiacenta[x][i].first]++;

                    if(!apartCoada[lisAdiacenta[x][i].first]) {
                        coada.push(lisAdiacenta[x][i].first);
                        apartCoada[lisAdiacenta[x][i].first] = 1;
                    }
                    if(viz[lisAdiacenta[x][i].first] >= nrNoduri) {
                        faraCiclNeg = 0;
                    }
                }
    }
    if(!faraCiclNeg)
        distBMF.clear();
    return distBMF;
}

vector<int> GrafCuCost :: Dijkstra(const int start)
{
    //minHeap ordonat dupa cost
    priority_queue< pair<int, int>, vector <pair<int, int> >, greater<pair<int, int>>> pQueue;
    vector<int> distDij(nrNoduri + 1, INF);
    vector<bool> apartPQ(nrNoduri+ 1, 0);
    pQueue.push(make_pair(0, start)), distDij[start] = 0;

    while (!pQueue.empty()) {
        int x = pQueue.top().second;
        pQueue.pop();
        if (!apartPQ[x]) {
            apartPQ[x] = 1;
            for (int i = 1; i < lisAdiacenta[x].size(); i++)
                if (distDij[lisAdiacenta[x][i].first] > distDij[x] + lisAdiacenta[x][i].second) {
                    distDij[lisAdiacenta[x][i].first] = distDij[x] + lisAdiacenta[x][i].second;
                    pQueue.push(make_pair(distDij[lisAdiacenta[x][i].first], lisAdiacenta[x][i].first));
                }
        }
    }
    return distDij;
}


//functie sablon utilizata cand sunt citite de la tastatura nr de noduri, nr de muchii si muchiile
GrafFaraCost CitireGrafFC(string numeFisier, string tipGraf) //https://infoarena.ro/problema/dfs - 100pc
{
    ifstream fin(numeFisier);

    int N, M;
    fin >> N >> M;

    GrafFaraCost graf(N, M);
    if(tipGraf == "neorientat") graf.citireNeorientatFC(fin);
    else graf.citireOrientatFC(fin);
    fin.close();
    return graf;
}

GrafCuCost CitireGrafCC(string numeFisier, string tipGraf) //https://infoarena.ro/problema/dfs - 100pc
{
    ifstream fin(numeFisier);

    int N, M;
    fin >> N >> M;

    GrafCuCost graf(N, M);
    if(tipGraf == "neorientat") graf.citireNeorientatCC(fin);
    else graf.citireOrientatCC(fin);
    fin.close();
    return graf;
}

///Corpurile functiilor
void Rezolva_DFSComponenteConexe(string fisierIntrare, string fisierIesire) //https://infoarena.ro/problema/dfs - 100pc
{
    ofstream fout(fisierIesire);
    fout << CitireGrafFC(fisierIntrare, "neorientat").nrCompConexe();
    fout.close();
}

void Rezolva_BFS(string fisierIntrare, string fisierIesire)  //https://www.infoarena.ro/problema/bfs - 100pc
{
    ifstream fin(fisierIntrare);
    ofstream fout(fisierIesire);

    int N, M, S;
    fin >> N >> M >> S;

    GrafFaraCost graf(N, M);
    graf.citireOrientatFC(fin);

    vector<int> rez = graf.BFS(S);
    for(int i = 1; i < rez.size() ; ++i) {
                fout << rez[i] << " ";
    }
    fout.close();
}

void Rezolva_SortareTopologica(string fisierIntrare, string fisierIesire)   //https://infoarena.ro/problema/sortaret - 100pc
{
    ofstream fout(fisierIesire);
    stack<int> rez = CitireGrafFC(fisierIntrare, "orientat").sortareTopologica();
    while (!rez.empty()) {
        fout << rez.top() << " ";
        rez.pop();
    }
    fout.close();
}

//exemple: (DA:(5 5 5 5 5 5),(5 5 5 5 4 4),(3 3 3 3),(4 4 4 4 4),(2 2 1 1),(2 2 1 1 0),(2 0 1 2 1),(2 1 2 1 2 1 2 3)
//(NU:(5 5 5 5 5 4),(3 2 1 0), (3 3 3 3 3)
void Rezolva_Havel_Hakimi(string fisierIntrare, string fisierIesire)
{
    ifstream fin(fisierIntrare);
    ofstream fout(fisierIesire);
    vector<int> grade;
    int N, x;
    fin >> N;

    for (int i = 0; i < N; i++) {
        fin >> x;
        grade.push_back(x);
    }
    fin.close();
    fout << GrafFaraCost :: existaGraf(grade);
    fout.close();
}

void Rezolva_CTC(string fisierIntrare, string fisierIesire)      //https://infoarena.ro/problema/ctc - 100 pc
{
    vector<vector<int>> rez = CitireGrafFC(fisierIntrare, "orientat").CTC();
    ofstream fout(fisierIesire);
    fout << rez.size() << "\n";
    for (int i = 0; i < rez.size(); ++i) {
        for (int j = 0; j < rez[i].size(); ++j) {
            fout << rez[i][j] << " ";
        }
        fout << "\n";
    }
    fout.close();
}


void Rezolva_Critical_Connection()    //https://leetcode.com/problems/critical-connections-in-a-network/  - Accepted
{
    int N, M;
    cin >> N >> M;

    GrafFaraCost graf(N, M);
    graf.citireNeorientatFC(cin);
    vector<vector<int>> rez =  graf.CriticalConnections();

    cout << "[";
    for(int i = 0; i < rez.size() ; ++i) {
                cout << "[" << rez[i][0] << "," << rez[i][1] << "]";
    }
     cout << "]";
}

void Rezolva_Biconex(string fisierIntrare, string fisierIesire)    // https://infoarena.ro/problema/biconex  - 100 pc
{
    pair<int, string> rez = CitireGrafFC(fisierIntrare, "neorientat").Biconex();
    ofstream fout(fisierIesire);
    fout << rez.first << "\n";
    fout << rez.second;
    fout.close();
}

void Rezolva_APM(string fisierIntrare, string fisierIesire)    // https://infoarena.ro/problema/biconex  - 100 pc
{
    ofstream fout(fisierIesire);
    GrafCuCost graf = CitireGrafCC(fisierIntrare, "neorientat");
    vector<pair<int, pair<int, int>>> muchii =  graf.getLisMuchii();
    pair<int, vector<pair<int, int>>> rez = graf.Kruskal(muchii);

    fout << rez.first << "\n";
    fout << rez.second.size() - 1 << "\n";
    for(int i = 1; i < rez.second.size(); ++i)
        fout << rez.second[i].first << " " << rez.second[i].second << "\n";
}


void Rezolva_Dijkstra(string fisierIntrare, string fisierIesire)    // https://infoarena.ro/problema/biconex  - 100 pc
{
    ofstream fout(fisierIesire);
    vector<int> distDij = CitireGrafCC(fisierIntrare, "orientat").Dijkstra(1);

    for(int i = 2; i < distDij.size(); i++)
        if(distDij[i] == INF) fout << 0 << " ";
        else fout << distDij[i] << " ";
}

void Rezolva_BMF(string fisierIntrare, string fisierIesire)    // https://infoarena.ro/problema/biconex  - 100 pc
{
    ofstream fout(fisierIesire);
    vector<int> distBMF = CitireGrafCC(fisierIntrare, "orientat").BellmanFord(1);

    if(distBMF.size()) {
        for(int i = 2; i < distBMF.size(); i++) {
             fout << distBMF[i] << " ";
             }
    }
   else
        fout << "Ciclu negativ!";
}

void Rezolva_Disjoint(string fisierIntrare, string fisierIesire)
{
    ifstream fin(fisierIntrare);
    ofstream fout(fisierIesire);
    vector<bool> rez = Graf :: Disjoint(fin);

    for(int i = 0; i < rez.size(); i++)
        if(rez[i] == 0) fout << "NU\n";
        else fout << "DA\n";
    fin.close();
    fout.close();
}

///Driver code
int main()
{
    Rezolva_Biconex("biconex.in", "biconex.out");
    return 0;
}