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

int Exercitiu = 7;

ifstream fin;
ofstream fout;
class graf
{
    int n, m;
    vector<vector<int> > adj;

public:
    graf(const int &tip = 0);

    // tema bf-df
    void BFS(int);
    void DFS(int, bool *, int &);
    void sortaret(int, bool *, stack<int> &);
    void S_BFS();
    void S_DFS();
    void S_sortaret();

    // 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 darb();
};

graf::graf(const int &tip)
{

    switch (tip)
    {
    case 1:
    case 3:
    {
        int x, y;
        fin >> this->n >> this->m;
        if (tip == 1)
            fin >> x;
        this->adj.resize(n + 1);
        for (int i = 0; i < this->m; ++i)
        {
            fin >> x >> y;
            this->adj[x].push_back(y);
        }
        break;
    }
    case 2:
    {
        int x, y;
        fin >> this->n >> this->m;
        this->adj.resize(n + 1);
        for (int i = 0; i < this->m; ++i)
        {
            fin >> x >> y;
            this->adj[x].push_back(y);
            this->adj[y].push_back(x);
        }
        break;
    }
    default:
        break;
    }
}

void graf::S_BFS()
{
    ifstream h;
    int start;
    h.open("bfs.in", std::ifstream::in);
    h >> start >> start >> start;
    h.close();
    BFS(start);
}

void graf::BFS(int start)
{
    int dist[this->n + 1];
    for (int i = 1; i <= n; ++i)
        dist[i] = -1;
    int i = 0;
    vector<int> queue;
    queue.push_back(start);
    dist[start] = 0;
    while (i < queue.size())
    {
        int start = queue[i++];
        for (int i = 0; i < this->adj[start].size(); ++i)
            if (dist[this->adj[start][i]] == -1)
            {
                queue.push_back(this->adj[start][i]);
                dist[this->adj[start][i]] = dist[start] + 1;
            }
    }
    for (int i = 1; i <= n; ++i)
    {
        fout << dist[i] << " ";
    }
}

void graf::S_DFS()
{
    bool visited[this->n + 1];
    int cc;
    for (int i = 1; i <= this->n; ++i)
        visited[i] = false;
    cc = 0;
    for (int i = 1; i <= this->n; ++i)
        if (!visited[i])
        {
            cc++;
            DFS(i, visited, cc);
        }
    fout << cc;
}

void graf::DFS(int nod, bool visited[], int &cc)
{
    visited[nod] = true;
    for (int i = 0; i < this->adj[nod].size(); ++i)
        if (!visited[this->adj[nod][i]])
            DFS(this->adj[nod][i], visited, cc);
}

void graf::S_sortaret()
{
    bool visited[this->n + 1];
    stack<int> mystack;
    int i;
    for (i = 1; i <= this->n; ++i)
        visited[i] = false;
    for (i = 1; i <= this->n; ++i)
        if (!visited[i])
            sortaret(i, visited, mystack);
    while (!mystack.empty())
    {
        // afisam in postordine invers
        fout << mystack.top() << " ";
        mystack.pop();
    }
}

void graf::sortaret(int nod, bool visited[], stack<int> &mystack)
{
    visited[nod] = true;
    for (int i = 0; i < this->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
        {
            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;
    int i;
    fin >> this->n >> this->m;
    int value[this->n + 1]; // in value se retin distantele de la nodul src la restul
    vector<vector<pair<int, int> > > adj;
    adj.resize(this->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 < this->m; ++i)
    {
        int cost;
        fin >> x >> y >> cost;
        adj[x].push_back(make_pair(y, cost));
    }
    for (i = 1; i <= this->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 <= this->n; ++i)
        if (value[i] != inf)
            fout << value[i] << " ";
        else
            fout << 0 << " ";
}

void graf::royfloyd()
{
    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;
    }
}

int main()
{
    //cout<<"vlad";
    switch (Exercitiu)
    {
    case 1:
    {
        fin.open("bfs.in", std::ifstream::in);
        fout.open("bfs.out", std::ifstream::out);
        graf a(1);
        a.S_BFS();
        fin.close();
        fout.close();
        break;
    }
    case 2:
    {
        fin.open("dfs.in", std::ifstream::in);
        fout.open("dfs.out", std::ifstream::out);
        graf a(2);
        a.S_DFS();
        fin.close();
        fout.close();
        break;
    }
    case 3:
    {
        fin.open("sortaret.in", std::fstream::in);
        fout.open("sortaret.out", std::fstream::out);
        graf a(3);
        a.S_sortaret();
        fin.close();
        fout.close();
        break;
    }
    case 4:
    {
        fin.open("apm.in", std::fstream::in);
        fout.open("apm.out", std::fstream::out);
        graf a;
        a.apm();
        fin.close();
        fout.close();
        break;
    }
    case 5:
    {
        fin.open("disjoint.in", std::fstream::in);
        fout.open("disjoint.out", std::fstream::out);
        graf a;
        a.disjoint();
        fin.close();
        fout.close();
        break;
    }
    case 6:
    {
        fin.open("dijkstra.in", std::fstream::in);
        fout.open("dijkstra.out", std::fstream::out);
        graf a;
        a.dijkstra();
        fin.close();
        fout.close();
        break;
    }
    case 7: 
    {
        fin.open("royfloyd.in",std::fstream::in);
        fout.open("royfloyd.out",std::fstream::out);
        graf a;
        a.royfloyd();
        break;
    }
    default:
        break;
    }
}