#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <deque>
#include <queue>
#include <climits>
#include <string>
#include <tuple>
#include <cstring>
#define inf INT_MAX - 1000000
#define Nmax 100001
using namespace std;


int Exercitiu = 9;

ifstream fin;
ofstream fout;

class graf
{
    int noduri, muchii;
    vector<vector<int> > adj;

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);

    graf();

    void out();

    // tema bf-df
    void BFS(int);
    void DFS(vector<bool> &, int);
    void sortaret(int, bool *, stack<int> &);
    void ctc();
    void dfs1_ctc(int, vector<bool>, stack<int> );
    void dfs2_ctc(int, vector<int> &, vector<bool>, vector<vector<int> >);



    // tema apm
    void apm();
    void union_apm(int x, int y, int tata[], int rang[]);
    int find_apm(int x, int tata[]);
    void disjoint();
    void dijkstra();
    void dijkstra1();

    //tema lab 5
    void royfloyd();
    void dfs_darb(int curr, int diam, int nod_departe, int visited[]);

    //tema lab6
    void eulerian();
    void hamiltonian();
};

graf ::graf()
{
    noduri = 0;
    muchii = 0;
    adj.resize(0);
}

void graf ::out()
{
    fout << noduri << " " << muchii << endl;

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

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

    int nod_1, nod_2;

    adj.resize(numar_noduri + 1);

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

        adj[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;

    adj.resize(numar_noduri + 1);

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

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

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

    int nod_1, nod_2;

    adj.resize(numar_noduri + 1);

    while (fin >> nod_1 >> nod_2)
    {
        adj[nod_1].push_back(nod_2);
        adj[nod_2].push_back(nod_1);
    }
}
	
void graf ::BFS(int start)
{ 
    int dist[noduri + 1];
    for (int i = 1; i <= noduri; i++)
        dist[i] = -1;

    bool visited[noduri + 1];
    for (int i = 1; i <= noduri; i++)
        visited[i] = false;

    queue<int> q;
    q.push(start);
    dist[start] = 0;
    visited[start] = true;

    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (unsigned int index = 0; index < adj[nod].size(); index++)
            if (visited[adj[nod][index]] == false)
            {
                q.push(adj[nod][index]);
                visited[adj[nod][index]] = true;
                dist[adj[nod][index]] = dist[nod] + 1;
            }
    }
    for (int secondIndex = 1; secondIndex <= noduri; secondIndex++)
        fout << dist[secondIndex] << " ";
}

void graf ::DFS(vector<bool> &visited, int start)
{
    visited[start] = true;
    for (unsigned int index = 0; index < adj[start].size(); index++)
        if (visited[adj[start][index]] == false)
            DFS(visited, adj[start][index]);
}

void graf::sortaret(int nod, bool visited[], stack<int> &mystack)
{
    visited[nod] = true;
    for (int i = 0; i < adj[nod].size(); ++i)
        if (!visited[adj[nod][i]])
        {
            sortaret(adj[nod][i], visited, mystack);
        }
    // introducem nodurile in postordine (dupa ce ies din stiva) in stiva solutie
    mystack.push(nod);
}

// void graf::dfs1_ctc(int nod, vector<bool>visited, stack<int> mystack){
//     visited[nod] = true;
//     for (int i = 0; i < adj[nod].size(); i++)
//     {
//         int curr = adj[nod][i];
//         if (visited[curr] == false)
//             dfs1_ctc(curr, visited, mystack);
//     }
//     mystack.push(nod); // se pun in stack nodurile parcurse
// }

// void dfs2_ctc(int nod, vector<int> &vtemp, vector<bool> visitedT, vector<vector<int> > adjT)
// {
//     //cout<<nod<<" ";
//     vtemp.push_back(nod);
//     visitedT[nod] = true;
//     for (int i = 0; i < adjT[nod].size(); i++)
//     {
//         int curr = adjT[nod][i];
//         if (visitedT[curr] == false)
//             dfs2_ctc(curr, vtemp, visitedT, adjT);
//     }
// }

// void graf::ctc()
// {
//     vector<vector<int> > adj, adjT, ctc;
//     vector<bool> visited, visitedT;
//     stack<int> mystack;
//     int n, m, x, y;
//     fin >> n >> m;
//     adj = vector<vector<int> >(n + 1);  // adiacenta
//     adjT = vector<vector<int> >(n + 1); // adiacenta transpusa
 
//     for (int i = 1; i <= m; i++)
//     {
//         fin >> x >> y;
//         adj[x].push_back(y);
//         adjT[y].push_back(x);
//     }
//     visited = vector<bool>(n + 1, false);
 
//     int nr = 0;
//     // pas 1 facem dfs normal si obtinem nodurile in stack
//     for (int i = 1; i <= n; i++)
//         if (visited[i] == false)
//             dfs1_ctc(i, visited, mystack);
 
//     ctc = vector<vector<int> >(n + 1);     // comp tare conexe
//     visitedT = vector<bool>(n + 1, false); //vectorul de visitede pt transpusa
//     //vector<int> vtemp;
//     int top;
//     // pas 2 scoatem pe rand elem din mystack si pt fiecare facem dfs incepand de la el
//     //cand se face dfs2 pe transpusa se iau pas cu pas ctc iar pt a trece la urm ctc trb facut asta "manual"
//     while (!mystack.empty())
//     {
//         top = mystack.top();
//         mystack.pop();
//         if (visitedT[top] == false)
//         {
//             vector<int> vtemp;
//             dfs2_ctc(top, vtemp, visitedT, adjT); // in vtemp se stockeaza pe rand comp conexe iar apoi se copiaza in ctc care va fi si reziltatul finl
//             ctc.push_back(vtemp);
//             nr++;
//         }
//     }
 
//     fout << nr << endl;
 
//     //cout<<ctc.size() << endl;
//     bool ok;
//     for (int i = 0; i < ctc.size(); i++)
//     {
//         ok = false;
//         for (int j = 0; j < ctc[i].size(); j++)
//         {
//             fout << ctc[i][j] << " ";
//             ok = true;
//         }
//         if (ok)
//             fout << endl;
//     }
// }

int graf::find_apm(int nod, int parents[]) // gasim parintele absolut al lui x
{
    while (nod != parents[nod])
    {
        nod = parents[nod];
        find_apm(nod, parents);
    }
    return nod;
}

void graf::union_apm(int x, int y, int parents[], int rank[]) // union by RANK legam arb mic de cel mare
{
    x = find_apm(x, parents); // in x se va memora parintele abs al acestuia
    y = find_apm(y, parents); // in y se va memora parintele abs al acestuia

    if (rank[x] > rank[y]) // mai mare
        parents[y] = x;

    else if (rank[x] < rank[y]) // mai mic
        parents[x] = y;
    else // daca este egal atunci vine conditia de a actualiza rank
    {
        parents[x] = y;
        rank[y] += 1;
    }
}

void graf::apm()
{
    vector<pair<int, pair<int, int> > > adj_cost; // m.first == costul, m.second.first = x, m.second.second = y;
    vector<pair<int, int> > mst;
    int n, m, parents[Nmax], rank[Nmax];
    int x, y, cost;
    fin >> n >> m;
    // int parents[this->n+1], rank[this->n+1];
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> cost;
        adj_cost.push_back(make_pair(cost, make_pair(x, y)));
    }

    for (int i = 0; i < n; i++) // initializare
    {
        parents[i] = i; // parintele
        rank[i] = 1;    // dimensiunea arborelui (cati copii are in total) => initial fiecare nod reprez un arbore form doar din rad
    }

    cost = 0;
    sort(adj_cost.begin(), adj_cost.end()); // sortam adj dupa cost
    for (auto muchie : adj_cost)
    {
        if (find_apm(muchie.second.first, parents) != find_apm(muchie.second.second, parents)) // nodurile au parinti abs dif deci facem union pt ca nu sunt in aceasi comp
        {
            mst.push_back(muchie.second);                                        // punem muchia in mst
            union_apm(muchie.second.first, muchie.second.second, parents, rank); // facem union intre cele 2 noduri
            cost += muchie.first;                                                // incrementam costul final
        }
    }

    fout << cost << endl
         << mst.size() << endl;
    for (int i = 0; i < mst.size(); i++)
    {
        fout << mst[i].first << " " << mst[i].second << "\n";
    }
}

void graf::disjoint()
{
    int n, m;
    fin >> n >> m;
    int parents[n + 1];
    int rank[n + 1];
    for (int i = 0; i <= n; ++i)
    {
        parents[i] = 0;
        rank[i] = 1;
    }
    int op, x, y;
    while (fin >> op >> x >> y)
    {
        if (op == 1) // union by rank
        {
            //union_apm(x,y,parents,rank);
            while (parents[x] != 0)
                x = parents[x]; // la final in x va fi parintele abs al acestuia la fel si in y
            while (parents[y] != 0)
                y = parents[y];
            int rx = rank[x];
            int ry = rank[y];
            // x=y deci au  aceasi parinti abs atunci deja fac parte din aceasi comp deci nu facem nimic
            // cazurile sunt pt noduri ce nu sunt deja in aceasi comp si trb facut "union"

            // union leaga parinte abs de parinte abs si il leaga pe cel cu intaltimea mai mica la cel cu inaltimea mai mare
            if (rx < ry) //
                parents[x] = y;

            else if (rx > ry)
                parents[y] = x;
            else // daca rankurile sunt egale deci oricare poate fi parinte si incrementam rank
            {
                parents[x] = y;
                rank[y] += 1;
            }
        }
        else // find + compression
        {
            int pa_x = x, pa_y = y, aux; // pa_x = parintele absolut al lui x , similar pa_y
            while (parents[pa_x] != 0)   // gasim parintele abs al lui x
                pa_x = parents[pa_x];
            while (parents[pa_y] != 0) // gasim parinte abs al lui y
                pa_y = parents[pa_y];
            if (pa_x == pa_y) // x si y au aceaselasi parinte absolut
                fout << "DA\n";
            else
                fout << "NU\n";
            while (x != pa_x) // actualizam parintii absoluti pt actualul x si pt restul nodurilor legat de el
            {
                aux = parents[x];
                parents[x] = pa_x;
                x = aux;
            }
            while (y != pa_y) // actualizam parintii absoluti pt actualul y si pt restul nodurilor legat de el
            {
                aux = parents[y];
                parents[y] = pa_y;
                y = aux;
            }
        }
    }
}

void graf::dijkstra()
{
    int x, y, n, m;
    int i;

    fin >> n >> m;
    int value[n + 1]; // in value se retin distantele de la nodul src la restul
    vector<vector<pair<int, int> > > adj;
    adj.resize(n + 1);
    set<pair<int, int> > set_cost_nod; // set_cost_nod retine nodurile inca neprocesate si costul pt a ajunge in ele
    // folosim set pt ca atunci cand vom lua un alt nod vrem sa il luam pe cel cu costul minim
    //  ce se afla la un mom de timp in set_nod_cost, inseamna ca acele noduri nu au fost inca procesate.
    for (int i = 0; i < m; ++i)
    {
        int cost;
        fin >> x >> y >> cost;
        adj[x].push_back(make_pair(y, cost));
    }
    for (i = 1; i <= n; ++i)
    {
        value[i] = inf; // retine costurile plecand in nod src
    }
    value[1] = 0;
    set_cost_nod.insert(make_pair(0, 1)); // cost 0 pt nodul sursa 1
    while (!set_cost_nod.empty())
    {
        int nod = (*set_cost_nod.begin()).second; // luam nodul curent
        set_cost_nod.erase(set_cost_nod.begin()); // pop nod crr si cost
        for (int i = 0; i < adj[nod].size(); ++i)
        {
            int nod_dest = adj[nod][i].first;             // nod_dest = este nodul destinatie de la care plecam din nodul crr("nod")
            int cost_dest = adj[nod][i].second;           // costul muchiei de la nod la nod_dest
            if (value[nod] + cost_dest < value[nod_dest]) // value[nod] retine dist de la nodul src(1) la nodul crr (nod)
            // adugam costul de la nod crr la nod dest sa vedem daca gasim o cale mai "ieftina" din nodul src(1) la nod dest
            {
                if (value[nod_dest] != inf)
                {
                    set_cost_nod.erase(set_cost_nod.find(make_pair(value[nod_dest], nod_dest)));
                    // in cazul in care value[nod_dest] !=inf adica dist din 1 la nod_dest a mai fost actualizata si totusi s-a gasit
                    // un drum mai scurt, vom scoate valoarea veche din set_nod_cost pt a o reactualiza mai jos in value si pt a face push
                    // in set la noua valoare pt nod_dest
                }
                // deci se respecta cond din if
                value[nod_dest] = value[nod] + cost_dest;                  // actualizam noul cost pt nodul dest
                set_cost_nod.insert(make_pair(value[nod_dest], nod_dest)); // inseram in set (costul de a ajung din src la nod_dest, nod dest)
                // la urmatoarele iteratii se va lua nod_dest ca fiind noul nod crr
            }
        }
    }
    for (int i = 2; i <= n; ++i)
        if (value[i] != inf)
            fout << value[i] << " ";
        else
            fout << 0 << " ";
}

void graf::royfloyd()
{
    int n;
    int dist[101][101];
    int i,j,k;
    fin>>n;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j) //citire
        {
            fin>>dist[i][j];
            if (dist[i][j]==0)
                dist[i][j]=inf;
        }
 
    for (k=1; k<=n; ++k) // luam pe rand nodurile noi pt a gasi un drum alternativ
        for (i=1; i<=n; ++i) // nodul sursa
            for (j=1; j<=n; ++j) //nodul dest
                {
                    if(dist[i][k]==inf || dist[k][j]==inf) // nu sunt cunoscute dist
                        continue;
                    else if (dist[i][k]+dist[k][j]<dist[i][j]) //gasim un drum alternativ mai scurt
                        dist[i][j]=dist[i][k]+dist[k][j]; //actualizam
                }
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=n; ++j)
            if (dist[i][j]==inf || i==j)
                fout<<0<<" ";
            else
                fout<<dist[i][j]<<" ";
        fout<<endl;
    }
}

void graf::dfs_darb(int curr, int diam, int nod_departe, int visited[]){
    for(int i = 0; i < adj[curr].size(); i++)
    {
        if(visited[adj[curr][i]] == 0)
        {
            visited[adj[curr][i]]=visited[curr];
            visited[adj[curr][i]]++;
            if(visited[adj[curr][i]] > diam)
            {
                nod_departe = adj[curr][i];
                diam=visited[adj[curr][i]];
            }
            dfs_darb(adj[curr][i], diam, nod_departe, visited);
        }
    }
}
// void graf::eulerian(){
//     int n,m,x,y;
//     fin>>n>>m;
//     vector<vector<int> > adj;
//     adj.resize(n+1);
//     int v1[m],v2[m];
//     bool visited[m];
//     for (int i=0; i<m; ++i)
//     {
//         fin>>x>>y;
//         adj[x].push_back(i);
//         adj[y].push_back(i);
//         v1[i]=x;
//         v2[i]=y;
//         visited[i]=false;
//     }
//     for (int i=1; i<=n; ++i)
//         if (adj[i].size()%2!=0 || adj[i].size()==0)
//         {
//             fout<<"-1";
//             return;
//         }
//     stack <int> stk;
//     vector <int> sol;
//     stk.push(1);
//     while (!stk.empty())
//     {
//         int nod=stk.top();
//         if (adj[nod].size()>0)
//         {
//             int muchie=adj[nod].back();
//             adj[nod].pop_back();
//             if (!visited[muchie])
//             {
//                 int vecin;
//                 if (nod!=v1[muchie])
//                     vecin=v1[muchie];
//                 else
//                     vecin=v2[muchie];
//                 visited[muchie]=true;
//                 stk.push(vecin);
//             }
//         }
//         else
//         {
//             stk.pop();
//             sol.push_back(nod);
//         }
//     }
//     for (int i=0; i<sol.size()-1; ++i)
//         fout<<sol[i]<<" ";
// }


int main()
{
    //cout<<"vlad";
    switch (Exercitiu)
    {
    case 1:
    {
        fin.open("bfs.in", std::ifstream::in);
        fout.open("bfs.out", std::ifstream::out);

        int n, m, s;
        fin >> n >> m >> s;

        graf graf(n, m, s);
        graf.BFS(s);
        
        fin.close();
        fout.close();
        break;
    }
    case 2:
    {
        int n, m;
        fin.open("dfs.in", std::ifstream::in);
        fout.open("dfs.out", std::ifstream::out);
        fin >> n >> m;

        vector<bool> visited;
        visited.resize(n + 1);
        for (int index = 1; index <= n; index++)
            visited[index] = false;

        graf graf(n, m);

        int contor = 0;
        for (int index = 1; index <= n; index++)
        {
            if (visited[index] == false)
            {
                graf.DFS(visited, index);
                contor++;
            }
        }
        fout << contor;
        fin.close();
        fout.close();
        break;
    }
    case 3:
    {
        int n, m;
        fin.open("sortaret.in", std::fstream::in);
        fout.open("sortaret.out", std::fstream::out);

        fin >> n >> m;
        graf graf(n,m,0);
        bool visited[n + 1];
        stack<int> mystack;
        int i;
        for (i = 1; i <= n; ++i)
            visited[i] = false;
        for (i = 1; i <= n; ++i)
            if (!visited[i])
                graf.sortaret(i, visited, mystack);
        while (!mystack.empty())
        {
        // afisam in postordine invers
            fout << mystack.top() << " ";
            mystack.pop();
        }
        fin.close();
        fout.close();
        break;
    }
    // case 4:
    // {
    //     fin.open("ctc.in", std::fstream::in);
    //     fout.open("ctc.out", std::fstream::out);
    //     graf a;
    //     a.ctc();
    //     fin.close();
    //     fout.close();
    //     break;
    // }
    case 5:
    {
        fin.open("apm.in", std::fstream::in);
        fout.open("apm.out", std::fstream::out);
        graf graf;
        graf.apm();
        fin.close();
        fout.close();
        break;
    }
    case 6:
    {
        fin.open("disjoint.in", std::fstream::in);
        fout.open("disjoint.out", std::fstream::out);
        graf graf;
        graf.disjoint();
        fin.close();
        fout.close();
        break;
    }
    case 7:
    {
        fin.open("dijkstra.in", std::fstream::in);
        fout.open("dijkstra.out", std::fstream::out);
        graf graf;
        graf.dijkstra();
        fin.close();
        fout.close();
        break;
    }
    case 8: 
    {
        fin.open("royfloyd.in",std::fstream::in);
        fout.open("royfloyd.out",std::fstream::out);
        graf graf;
        graf.royfloyd();
        fin.close();
        fout.close();
        break;
    }
    case 9: 
    {
        vector<int> adj[100001];
        int visited[100001];
        int diam=0, nod_departe=0;
        int n;
        fin.open("darb.in",std::fstream::in);
        fout.open("darb.out",std::fstream::out);
        fin>>n;
        for(int i=1; i <= n; ++i)
            visited[i] = 0;
        graf graf(n);
        visited[1]=1;
        graf.dfs_darb(1, diam, nod_departe, visited);
        diam=0;
        memset(visited, 0, sizeof(visited));
        visited[nod_departe] = 1;
        graf.dfs_darb(nod_departe, diam, nod_departe, visited);
        fout << diam;
        break;
    }
    // case 10: 
    // {
    //     fin.open("ciclueuler.in",std::fstream::in);
    //     fout.open("ciclueuler.out",std::fstream::out);
    //     graf a;
    //     a.eulerian();
    //     break;
    // }
    default:
        break;
    }
    return 0;
}