#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;
    vector<int> lista;
    vector< vector<pair<int,int> > > adj_pair;
    vector<vector<int> > adjT;

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 ctc);
    graf();

    // tema bf-df
    void BFS(int);
    void DFS(vector<bool> &, int);
    void sortaret(int, bool *, stack<int> &);
    void ctc();
    void dfs_ctc(int nod, vector <bool> &visited, stack<int> &mystack, vector<vector<int> > adj);

    // 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[]);
    void darb();

    //tema lab6
    int eulerian();
    void hamiltonian();
    bool bfs_cuplaj(int st[], int dr[], int dist[]);
    bool dfs_cuplaj(int nod, int st[], int dr[], int dist[]);
    void cuplaj();
};

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

graf ::graf(int numar_noduri, int numar_muchii, int aux)
{
    noduri = numar_noduri;
    muchii = numar_muchii;
    int x, y;
    adj.resize(numar_noduri + 1);

    for (int i = 1; i <= numar_muchii; i++)
    {
        fin >> x >> y;
        adj[x].push_back(y);
    }
}

graf ::graf(int numar_noduri, int numar_muchii)
{
    noduri = numar_noduri;
    muchii = numar_muchii;
    int x, y;
    adj.resize(numar_noduri + 1);

    for (int i = 1; i <= numar_muchii; i++)
    {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

graf ::graf(int numar_noduri)
{
    noduri = numar_noduri;
    int x, y;
    adj.resize(numar_noduri + 1);
    while (fin >> x >> y)
    {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

graf ::graf(int numar_noduri, int numar_muchii, string ctc){
    noduri = numar_noduri;
    muchii = numar_muchii;
    int x, y;
    adj.resize(numar_noduri + 1);
    for (int i = 1; i <= numar_muchii; i++)
    {
        fin >> x >> y;
        adj[x].push_back(y);
        adjT[y].push_back(x);
    }
}

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 (int i = 0; i < adj[nod].size(); i++)
            if (visited[adj[nod][i]] == false)
            {
                q.push(adj[nod][i]);
                visited[adj[nod][i]] = true;
                dist[adj[nod][i]] = dist[nod] + 1;
            }
    }
    for (int i = 1; i <= noduri; i++)
        fout << dist[i] << " ";
}

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

void graf::dfs_ctc(int nod, vector <bool> &visited, stack<int> &mystack, vector<vector<int> >adj) {
    mystack.push(nod);
    visited[nod] = true;
    for (int i = 0; i < adj[nod].size(); i++)
    {
        int curr = adj[nod][i];
        if (visited[curr] == false)
            dfs_ctc(curr, visited, mystack, adj);
    }
}

void graf::ctc(){
    fin>>noduri >> muchii;
    int x , y;
    adj.resize(noduri+1);
    adjT.resize(noduri+1);
    for (int i=1; i<=muchii; i++)
    {
        fin>>x >> y;
        adj[x].push_back(y);
        adjT[y].push_back(x);
    }
    vector<bool> visited, visitedT;
    stack <int> mystack1, mystack2;
    //mystack = stack <int> (noduri+1);
    visited = vector<bool>(noduri + 1, false);
    visitedT = vector<bool>(noduri + 1, false); //vectorul de vizitate pt transpusa
    //vector<int> vtemp;
    vector<stack<int> >ctc;
    ctc = vector<stack<int> >(noduri + 1);     // comp tare conexe
    int nr = 0;
    // pas 1 facem dfs normal si obtinem nodurile in stack
    for (int i = 1; i <= noduri; i++)
        {if (visited[i] == false)
            {
                dfs_ctc(i, visited, mystack1, adj);
            }
        }
    // 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"
    for(int i =1; i<=noduri; i++)
    {
        if (visitedT[i] == false)
        {
            dfs_ctc(i, visitedT, mystack2, adjT); // in vtemp se stockeaza pe rand comp conexe iar apoi se copiaza in ctc care va fi si reziltatul finl
            ctc.push_back(mystack2);
            nr++;
        }
    }
 
    fout << nr << endl;

    for (int i = 1; i <= nr; i++)
    {
        while(ctc[ctc.size()-i].size()>0)
        {
            fout << ctc[ctc.size()-i].top() << " ";
            ctc[ctc.size()-i].pop();
        }
        fout << endl;
    }
}

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

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::darb(){
    fin>>noduri;
    adj.resize(noduri+1);
    for(int i=1; i<=noduri-1; i++)
    {
        int x, y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int visited[100001];
    int diam=0, nod_departe=0;  
    
    memset(visited,0,sizeof(visited));
    visited[1]=1;

    dfs_darb(1, diam, nod_departe, visited);
    
    diam=0;
    memset(visited,0,sizeof(visited));
    visited[nod_departe]=1;

    dfs_darb(nod_departe, diam, nod_departe, visited);
    fout<<diam;
}

int graf::eulerian(){
    int x, y;
    fin >> noduri >> muchii;
    adj.resize(noduri + 1);

    int from[muchii], to[muchii];
    bool visited[muchii];

    for (int i = 0; i < muchii; i++)
    {
        fin >> x >> y;

        adj[x].push_back(i);
        adj[y].push_back(i);

        from[i] = x;
        to[i] = y;
        visited[i] = false;
    }

    for (int i = 1; i < noduri + 1; i++)
        if (adj[i].size() % 2 != 0 || adj[i].size() == 0)
        {
            fout << "-1\n";
            return 0;
        }

    vector<int> sol;
    stack<int> stk;
    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 != from[muchie])
                    vecin = from[muchie];
                else
                    vecin = to[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] << " ";
    return 1;
}

bool graf::bfs_cuplaj(int st[],int dr[],int dist[])
{
    queue<int> q;
    for (int i=1; i<=noduri; ++i)
        if (st[i]==0)
        {
            dist[i]=0;
            q.push(i);
        }
        else
            dist[i]=inf;
    dist[0]=inf;
    while (!q.empty())
    {
        int curr=q.front();
        q.pop();
        if (dist[curr]<dist[0])
            for (int i=0; i<adj_pair[curr].size(); ++i)
            {
                int vecin=adj_pair[curr][i].first;
                if (dist[dr[vecin]]==inf)
                {
                    dist[dr[vecin]]=dist[curr]+1;
                    q.push(dr[vecin]);
                }
            }
    }
    return dist[0]!=inf;
}

bool graf::dfs_cuplaj(int nod, int st[], int dr[], int dist[])
{
    if (nod!=0)
    {
        for (int i=0; i<adj_pair[nod].size(); ++i)
        {
            int vecin=adj_pair[nod][i].first;
            if (dist[dr[vecin]]==dist[nod]+1)
                if (dfs_cuplaj(dr[vecin],st,dr,dist))
                {
                    dr[vecin]=nod;
                    st[nod]=vecin;
                    return true;
                }
        }
        dist[nod]=inf;
        return false;
    }
    return true;
}

void graf::cuplaj(){
    int nrmuchii, x, y, sol=0;
    fin>>noduri >>muchii >>nrmuchii;
    adj_pair.resize(noduri+1);
    for(int i=0; i<nrmuchii; i++)
    {
        fin >> x >> y;
        adj_pair[x].push_back(make_pair(y,0));
    }
    int st[noduri+1],dr[muchii+1],dist[noduri+1];
    memset(st, 0, sizeof(st));
    memset(dr, 0, sizeof(dr));
    while (bfs_cuplaj(st,dr,dist))
    {
        for (int i=1; i<=noduri; ++i)
            if (st[i]==0 && dfs_cuplaj(i,st,dr,dist))
                ++sol;
    }
    fout<<sol<<endl;
    for (int i=0; i<=noduri; ++i)
        if (st[i])
            fout<<i<<" "<<st[i]<<endl;
}

int main()
{
    //cout<<"vlad";
    switch (Exercitiu)
    {
    case 1: //bfs
    {
        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: //dfs
    {
        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: //sortaret
    {
        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: //ctc 
    {
        fin.open("ctc.in", std::fstream::in);
        fout.open("ctc.out", std::fstream::out);
        graf graf;
        graf.ctc();
        fin.close();
        fout.close();
        break;
    }
    case 5: //apm
    {
        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: //disjoint
    {
        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: //dijkstra
    {
        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: //royfloyd
    {
        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: // darb 
    {
        fin.open("darb.in",std::fstream::in);
        fout.open("darb.out",std::fstream::out);
        graf graf;
        graf.darb();
        fin.close();
        fout.close();
        break;

    }
    case 10: //ciclu euler
    {
        fin.open("ciclueuler.in", std::ifstream::in);
        fout.open("ciclueuler.out", std::ifstream::out);
        graf graf;
        graf.eulerian();
        fin.close();
        fout.close();
        break;
    }
    case 11: //cuplaj
    {
        fin.open("cuplaj.in", std::ifstream::in);
        fout.open("cuplaj.out", std::ifstream::out);
        graf graf;
        graf.cuplaj();
        fin.close();
        fout.close();
    }
    default:
        break;
    }
    return 0;
}