#include <bits/stdc++.h>

using namespace std;

ifstream f;
ofstream g;

class Graf {

    int noduri, muchii;

    vector< vector<int> > lista;

    public:

    Graf(int numar_noduri, int numar_muchii, int aux);

    Graf(int numar_noduri, int numar_muchii);

    Graf(int numar_noduri);

    Graf(int numar_noduri, int numar_muchii, string apm);

    void out();

    void bfs(int start);

    void dfs(vector<bool> &vizitat, int start);

    void biconex();

    void dfs_biconex(int start, vector<bool> &vizitat, int niv, vector<int> &nivel, vector<int> &nivel_intoarcere, vector<int> &parinte, vector < pair <int, int> > &st, int &contor, vector<set<int>> &componeneteBiconexe);

    void componenteTareConexe(int nod, vector<int> &rezultat, vector <int> &nivel, vector <int> &nivelMinim, vector <bool> &stiva, stack <int> &st, vector < vector <int> > &output, int adancime);

    void sortaret(int start, vector<bool> &vizitat, vector<int> &output);

    bool Havel_Hakimi(int n, vector<int> &grade);

    void critical();

    void dfs_critical(int nod, int nodAnterior, vector<int> &nivel, vector<int> &nivelMinim, vector< vector <int> > &output, int adancime);

    void apm();

    int apm_min(int muchie[], bool ales[]);
};

void Graf :: out ()
{
    g << noduri << " " << muchii << endl;

    for(int i = 0; i < noduri + 1; i++)
    {
        g << i << " : ";
        for(int j = 0 ; j < lista[i].size(); j++)
            g << lista[i][j] << " ";
        g << endl;
    }

}

Graf :: Graf (int numar_noduri, int numar_muchii, int aux)
{
    noduri = numar_noduri;
    muchii = numar_muchii;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    for(int i = 1; i <= numar_muchii; i++)
    {
        f >> nod_1 >> nod_2;

        lista[nod_1].push_back(nod_2);
    }
}

Graf :: Graf (int numar_noduri, int numar_muchii)
{
    noduri = numar_noduri;
    muchii = numar_muchii;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    for(int i = 1; i <= numar_muchii; i++)
    {
        f >> nod_1 >> nod_2;

        lista[nod_1].push_back(nod_2);
        lista[nod_2].push_back(nod_1);
    }
}

Graf :: Graf (int numar_noduri)
{
    noduri = numar_noduri;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    while(f >> nod_1 >> nod_2)
    {
        lista[nod_1].push_back(nod_2);
        lista[nod_2].push_back(nod_1);
    }
}

Graf :: Graf (int numar_noduri, int numar_muchii, string apm)
{
    noduri = numar_noduri;
    muchii = numar_muchii;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    for(int index = 1; index < noduri + 1; index++)
        for(int secondIndex = 1; secondIndex < noduri + 1; secondIndex++)
            lista[index].push_back(0);

    for(int index = 0; index < numar_muchii; index++)
    {
        f >> nod_1 >> nod_2 >> lista[nod_1][nod_2];
        lista[nod_2][nod_1] = lista[nod_1][nod_2];
    }
}

void Graf :: bfs(int start)
{
    int distanta[noduri + 1];

    for(int index = 1; index <= noduri; index++)
        distanta[index] = -1;

    bool vizitat[noduri + 1] = {false};

    queue<int> q;

    q.push(start);

    distanta[start] = 0;

    vizitat[start] = true;

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(int index = 0; index < lista[nod].size(); index++)
            if(vizitat[lista[nod][index]] == false)
            {
                q.push(lista[nod][index]);
                vizitat[lista[nod][index]] = true;
                distanta[lista[nod][index]] = distanta[nod] + 1;
            }
    }

    for(int secondIndex = 1; secondIndex <= noduri; secondIndex++)
        g << distanta[secondIndex] << " ";
}

void Graf :: dfs(vector<bool> &vizitat, int start)
{
    vizitat[start] = true;
    for(int index = 0; index < lista[start].size(); index++)
        if(vizitat[lista[start][index]] == false)
            dfs(vizitat, lista[start][index]);
}

void Graf :: biconex()
{
    int contor = 0;

    vector<bool> vizitat;
    vizitat.resize(noduri + 1);

    vector<int> nivel;
    vector<int> nivel_intoarcere;
    vector<int> parinte;
    vector< set <int> > componenteBiconexe;

    nivel.resize(noduri + 1);
    nivel_intoarcere.resize(noduri + 1);
    parinte.resize(noduri + 1);

    vector < pair<int, int>> st;

    for(int index = 1; index <= noduri; index++)
    {
        nivel[index] = 0;
        nivel_intoarcere[index] = 0;
        vizitat[index] = false;
    }


    for(int index = 1; index <= noduri; index++)
    {
        if(vizitat[index] == false)
        {
            dfs_biconex(index, vizitat, 1, nivel, nivel_intoarcere, parinte, st, contor, componenteBiconexe);

            int j = 0;

            set<int> set_aux;

            while(!st.empty())
            {
                j = 1;
                set_aux.insert(st.back().first);
                set_aux.insert(st.back().second);
                st.pop_back();
            }

            componenteBiconexe.push_back(set_aux);

            if(j == 1)
            {
                contor++;
            }
        }
    }

    g << contor << endl;

    for(int index = 0; index < componenteBiconexe.size(); index++)
    {
        set<int>::iterator it;

        for(it = componenteBiconexe[index].begin(); it != componenteBiconexe[index].end(); it++)
            g << *it << " ";
        g << endl;
    }
}

void Graf :: dfs_biconex(int start, vector<bool> &vizitat, int niv, vector<int> &nivel, vector<int> &nivel_intoarcere, vector<int> &parinte, vector < pair < int, int> > &st, int &contor, vector<set<int>> &componenteBiconexe)
{

    vizitat[start] = true;
    nivel[start] = nivel_intoarcere[start] = niv;

    int copil = 0;

    for(int index = 0; index < lista[start].size(); index++)
    {
        int nod = lista[start][index];

        if(vizitat[nod] == false)
            {
                copil++;
                parinte[nod] = start;

                pair<int, int> aux;
                aux.first = start;
                aux.second = nod;

                st.push_back(aux);

                dfs_biconex(nod, vizitat, niv + 1, nivel, nivel_intoarcere, parinte, st, contor, componenteBiconexe);

                nivel_intoarcere[start] = min(nivel_intoarcere[start], nivel_intoarcere[nod]);

                if( (nivel[start] == 1 && copil > 1) || (nivel[start] > 1 && nivel_intoarcere[nod] >= nivel[start]) )
                {
                    set<int> set_aux;

                    while(st.back().first != start || st.back().second != nod)
                    {
                        set_aux.insert(st.back().first);
                        set_aux.insert(st.back().second);
                        st.pop_back();
                    }


                    set_aux.insert(st.back().first);
                    set_aux.insert(st.back().second);

                    componenteBiconexe.push_back(set_aux);

                    st.pop_back();
                    contor++;
                }
            }
        else if(nod != parinte[start])
        {
            nivel_intoarcere[start] = min(nivel_intoarcere[start], nivel[nod]);
            if(nivel[nod] < nivel[start])
            {
                pair<int, int> aux;
                aux.first = start;
                aux.second = nod;

                st.push_back(aux);
            }
        }
    }
}

void Graf :: componenteTareConexe(int nod, vector<int> &rezultat, vector <int> &nivel, vector <int> &nivelMinim, vector <bool> &stiva, stack <int> &st, vector < vector <int> > &output, int adancime)
{
    nivel[nod] = adancime;
    nivelMinim[nod] = adancime;

    st.push(nod);

    stiva[nod] = true;

    for(int index = 0; index < lista[nod].size(); index++)
    {
        if(nivel[lista[nod][index]] == -1)
        {
            componenteTareConexe(lista[nod][index], rezultat, nivel, nivelMinim, stiva, st, output, adancime + 1);
            nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[lista[nod][index]]);
        }
        else if(stiva[lista[nod][index]])
            nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[lista[nod][index]]);
    }

    if(nivel[nod] == nivelMinim[nod])
    {
        rezultat.clear();
        int node;
        do
        {
            rezultat.push_back(node = st.top());
            st.pop();
            stiva[node] = false;
        }
        while(node != nod);

        output.push_back(rezultat);
    }
}

void Graf :: sortaret(int start, vector<bool> &vizitat, vector<int> &output)
{
    vizitat[start] = true;

    for(int index = 0; index < lista[start].size(); index++)
        if(vizitat[lista[start][index]] == false)
            sortaret(lista[start][index], vizitat, output);

    output.push_back(start);
}

bool Graf :: Havel_Hakimi(int n, vector<int> &grade)
{
    while(true)
    {
        sort(grade.begin(), grade.end(), greater<>());

        if(grade[0] == 0)
            return true;

        int nod = grade[0];

        grade.erase(grade.begin() + 0);

        if(nod > grade.size())
            return false;

        for(int index = 0; index < nod; index++)
        {
            grade[index]--;

            if(grade[index] < 0)
                return false;
        }
    }
}

void Graf :: critical()
{
    vector<int> nivel;
    vector<int> nivelMinim;
    vector< vector <int> > output;

    nivel.resize(noduri);
    nivelMinim.resize(noduri);

    int adancime = 1;

    dfs_critical(0, -1, nivel, nivelMinim, output, adancime);

    for(int index = 0; index < output.size(); index++)
    {
        for(int secondIndex = 0; secondIndex < output[index].size(); secondIndex++)
            g << output[index][secondIndex] << " ";
        g << endl;
    }
}

void Graf :: dfs_critical(int nod, int nodAnterior, vector<int> &nivel, vector<int> &nivelMinim, vector< vector <int> > &output, int adancime)
{
    nivel[nod] = nivelMinim[nod] = adancime;

    for(int index = 0; index < lista[nod].size(); index++)
    {
        int nodUrmator = lista[nod][index];

        if (nivel[nodUrmator] == 0)
        {
            dfs_critical(nodUrmator, nod, nivel, nivelMinim, output, adancime + 1);
            nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[nodUrmator]);
        }
        else
            if (nodUrmator != nodAnterior)
                nivelMinim[nod] = min(nivelMinim[nod], nivel[nodUrmator]);

        if (nivelMinim[nodUrmator] > nivel[nod])
            output.push_back({nod, nodUrmator});
        }
}

void Graf :: apm()
{
    int parinte[noduri + 1], muchie[noduri + 1];        // parinte - contine arborele de cost minim || muchie - contine muchia minima

    bool ales[noduri + 1];                              // ales - vector de bool pentru a verifica daca o muchie a fost adaugata sau nu

    for(int index = 1; index < noduri + 1; index++)
    {
        muchie[index] = INT_MAX;                        // Initializam totul cu o valaoare foarte mare pentru a putea sa determinam minimul
        ales[index] = false;                            // Marcam tot vectorul de muchii alese cu false
    }

    muchie[1] = 0;                                      // Mereu includem prima muchie in vector
    parinte[1] = -1;                                    // Primul nod e radacina deci parintele lui e -1

    for(int index = 1; index < noduri; index++)
    {
        int nod = apm_min(muchie, ales);                // Alegem cea mai mica muchie

        ales[nod] = true;                               // O marcam ca adaugata in vector

        for(int secondIndex = 1; secondIndex < noduri + 1; secondIndex++)
            if(lista[nod][secondIndex] && ales[secondIndex] == false && lista[nod][secondIndex] < muchie[secondIndex])  // Determinam cea mai mica muchie curenta
            {
                parinte[secondIndex] = nod;
                muchie[secondIndex] = lista[nod][secondIndex];
            }
    }

    long long int sum = 0;

    for(int index = 1; index < noduri + 1; index++)
        sum = sum + muchie[index];                      // Calculam suma costurilor

    g << sum << endl << noduri - 1;                     // Afisam suma si numarul de muchii

    for(int index = 2; index < noduri + 1; index++)
        g << endl << parinte[index] << " " << index;    // Afisam muchiile din arbore
}

int Graf :: apm_min(int muchie[], bool ales[])
{
    int minim = INT_MAX, min_index;                     // Initializam minimul cu o valaoare foarte mare pentru a putea sa il determinam

    for(int index = 1; index < noduri + 1; index++)
        if(ales[index] == false && muchie[index] < minim)       // Determinam cea mai mica muchie
        {
            minim = muchie[index];
            min_index = index;
        }

    return min_index;                                   // Dam return la indicele minimului
}

int main()
{
    int problema = 8;

    if(problema == 1)   // 100
    {
        f.open ("bfs.in", std::ifstream::in);
        g.open ("bfs.out", std::ifstream::out);

        int n, m, s;

        f >> n >> m >> s;

        Graf graf(n, m, s);

        graf.bfs(s);

        f.close();

        g.close();

    }

    if(problema == 2)   // 100
    {
        int n, m;

        f.open ("dfs.in", std::ifstream::in);
        g.open ("dfs.out", std::ifstream::out);

        f >> n >> m;

        vector<bool> vizitat;

        vizitat.resize(n + 1);

        for(int index = 1; index <= n; index++)
            vizitat[index] = false;

        Graf graf(n, m);

        int contor = 0;

        for(int index = 1; index <= n; index++)
        {
            if(vizitat[index] == false)
                {
                    graf.dfs(vizitat, index);
                    contor++;
                }
        }

        g << contor;

        f.close();
        g.close();
    }

    if(problema == 3)   // 90 - TLE
    {
        int n, m;

        f.open ("biconex.in", std::ifstream::in);
        g.open ("biconex.out", std::ifstream::out);

        f >> n >> m;

        Graf graf(n, m);

        graf.biconex();

        f.close();
        g.close();
    }

    if(problema == 4)   // 70
    {
        int n, m;

        f.open ("ctc.in", std::ifstream::in);
        g.open ("ctc.out", std::ifstream::out);

        f >> n >> m;

        Graf graf(n, m, 0);

        vector<int> rezultat;
        vector<int> nivel;
        vector<int> nivelMinim;
        vector<bool> stiva;
        vector< vector <int> > output;
        stack<int> st;

        nivel.resize(n + 1);
        nivelMinim.resize(n + 1);
        stiva.resize(n + 1);

        for(int index = 1; index <= n; index++)
        {
            nivel[index] = -1;
            stiva[index] = false;
        }

        for(int index = 1; index <= n; index++)
            if(nivel[index] == -1)
                graf.componenteTareConexe(index, rezultat, nivel, nivelMinim, stiva, st, output, 0);

        g << output.size() << "\n";

        for(int index = 0; index < output.size(); index++)
        {
            for(int secondIndex = 0; secondIndex < output[index].size(); secondIndex++)
                g << output[index][secondIndex] << " ";
            g << "\n";
        }

        f.close();
        g.close();
    }

    if(problema == 5)   // 100
    {
        int n, m;

        f.open ("sortaret.in", std::ifstream::in);
        g.open ("sortaret.out", std::ifstream::out);

        f >> n >> m;

        Graf graf(n, m, 0);

        vector<int> output;
        vector<bool> vizitat;

        vizitat.resize(n + 1);

        for(int index = 1; index <= n; index++)
            vizitat[index] = false;

        for(int index = 1; index <= n; index++)
            if(vizitat[index] == false)
                    graf.sortaret(index, vizitat, output);

        for(int index = output.size() - 1; index >= 0; index --)
            g << output[index] << " ";

    }

    if(problema == 6)   // 100
    {
        f.open ("havelhakimi.in", std::ifstream::in);
        g.open ("havelhakimi.out", std::ifstream::out);

        vector<int> grade;

        int n, grad;

        f >> n;

        grade.resize(n);

        for(int index = 0; index < n; index++)
        {
            f >> grad;
            grade.push_back(grad);
        }

        Graf graf(0, 0, 0);

        if(graf.Havel_Hakimi(n, grade))
            g << "Secventa de numere poate forma un graf.";
        else
            g << "Secventa de numere nu poate forma un graf.";

    }

    if(problema == 7)   // 100
    {
        f.open ("critical.in", std::ifstream::in);
        g.open ("critical.out", std::ifstream::out);

        int n;

        f >> n;

        Graf graf(n);

        graf.critical();
    }

    if(problema == 8)
    {
        f.open ("apm.in", std::ifstream::in);
        g.open ("apm.out", std::ifstream::out);

        int n, m;

        string graf_apm = "apm";

        f >> n >> m;

        Graf graf(n, m, graf_apm);

        graf.apm();
    }

    return 0;
}