#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 = 4;

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

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;
                rank[y]=max(ry,rx+1);
            }
            else
            {
                parents[y]=x;
                rank[x]=max(rx,ry+1);
            }
        }
        else // find + compression
        {
            int pa_x=x,pa_y=y,aux; // pa_x = parintele absolut al lui x , similar ry
            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; 
    }
    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::dijkstra1(){
    int x,y;
    fin>>this->n>>this->m;
    int m_adj[this->n][this->n];
    for (int i=1;i<=this->n;i++)
        for(int j=1;j<=this->n;j++)
            m_adj[i][j]=0;
    for (int i=1;i<=m;i++)
    {
        int cost;
        fin>>x>>y>>cost;
        m_adj[x][y]=cost;
        m_adj[y][x]=cost;
    }
    for (int i=1;i<=this->n;i++)
        {for(int j=1;j<=this->n;j++)
            fout<<m_adj[i][j]<<" ";
        fout<<endl;
        }
    int parent[this->n];		//Stores Shortest Path Structure
	vector<int> value(this->n,INT_MAX);	//Keeps shortest path values to each vertex from source
	vector<bool> processed(this->n,false);	//TRUE->Vertex is processed

	//Assuming start point as Node-0
	parent[1] = -1;	//Start node has no parent
	value[1] = 0;	//start node has value=0 to get picked 1st

	//Include (V-1) edges to cover all V-vertices
	for(int i=1;i<this->n;++i)
	{
		//Select best Vertex by applying greedy method
		int U;// = selectMinVertex(value,processed);
        int minimum = INT_MAX;
	int vertex;
	for(int i=1;i<=this->n;++i)
	{
		if(processed[i]==false && value[i]<minimum)
		{
			vertex = i;
			minimum = value[i];
		}
	}
    U=vertex;
		processed[U] = true;	//Include new Vertex in shortest Path Graph

		//Relax adjacent vertices (not yet included in shortest path graph)
		for(int j=1;j<=this->n;++j)
		{
			/* 3 conditions to relax:-
			      1.Edge is present from U to j.
			      2.Vertex j is not included in shortest path graph
			      3.Edge weight is smaller than current edge weight
			*/
			if(m_adj[U][j]!=0 && processed[j]==false && value[U]!=INT_MAX
			&& (value[U]+m_adj[U][j] < value[j]))
			{
				value[j] = value[U]+m_adj[U][j];
				parent[j] = U;
			}
		}
	}
	fout<<endl;
	for (int i=1;i<=this->n;i++)
    {
        fout<<value[i]<<" ";
    }

}
 
int main()
{
    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;
    }
    default:
        break;
    }
}