//
//  main.cpp
//  Cuplaj maxim in graf bipartit
//
//  Created by Mara Dascalu on 13/12/2021.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
//#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>
#include <tuple>

#define INF INT_MAX
#define NIL 0
#define N  100005
#define M  500001
typedef std::tuple<int, int, int> tpl;
typedef std:: pair<int, int> Pair;

using namespace std;

ifstream input("disjoint.in");
ofstream output("disjoint.out");

class DisjointSets
{
    int nodes;
    vector<int> reprez;     //vectorul care retine reprezentantul fiecarui nod

public:
    DisjointSets(int nodes);
    void initialization(int no_node);      //creeaza fiecare nod drept un subarbore
    int reprezentative(int node, int father[]);       //returneaza reprezentantul componentei care il contine pe node
    void reunite(int node1, int node2, int height[], int father[]); //uneste componenta care contine node1 cu cea care contine node2
};

DisjointSets::DisjointSets(int nodes)
{
    this->nodes = nodes;
}

void DisjointSets::initialization(int nodes)
{
    reprez.push_back(0);
    for (int i = 1 ; i <= nodes; i++)
    {
        reprez.push_back(0);
    }
}

int DisjointSets::reprezentative(int node, int father[])
{
    while (father[node])
        node = father[node];
    return node;
}

void DisjointSets::reunite(int node1, int node2, int height[], int father[])
{
    int r1, r2;

    r1 = reprezentative(node1, father);
    r2 = reprezentative(node2, father);

    if (height[r1] > height[r2])
        father[r2] = r1;
    else
    {
        father[r1] = r2;
        if (height[r1] == height[r2])
            height[r2]++;
    }
}

class Graph
{
    int nodes, edges, nodes_l, nodes_r;
    vector<int> adj[N] ;
    vector<Pair> adj_weight[N];
    vector<Pair> adj_capacity[N];

    void addEdgesDg(int nodes, int edges);
    void addEdgesUg ();
    void addEdgesDgWeight();
    void addEdgesDgCapacity();

    void dfs(int node, bool visited[]);     //parcurgerea DFS a grafului
    void outputAdj();       //afisarea vectorului de vectori de adiacenta a nodurilor
    static bool sortByThird (const tpl &a, const tpl&b);    //sorteaza vectorul de tupluri coare contine si costul muchiilor dupa al treilea parametru (cost)

    //PROBLEMA DFS INFOARENA: https://infoarena.ro/problema/dfs
    int calculateConnectedComponents(bool visited[]);
    
    //PROBLEMA bfs INFORARENA: https://infoarena.ro/problema/bfs
    vector<int> bfsUtil(int node, bool visited[]);    //bfs adaptat pentru a calcula costul de parcurgere al fiecarui nod, plecand dintr-un nod de start

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    void dfsBiconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<Pair> &component_node, int &current, bool visited[]);     // DFS auxiliar pentru determinarea componentelor biconexe

    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    void calculateIndegree (int indegree[]);       //functie auxiliara sortarii topologice pentru calcularea gradului interior al fiecarui nod
    vector<int> topSort(int indegree[], queue<int> queue_ts);      //functia de sortare topologica

    //PROBLEMA HAVEL-HAKIMI
    bool graphExists (vector<int> degree_seq);      //functia care decide daca daca o secventa de numere poate sau nu poate reprezenta o secventa de noduri ale unui graf
    void inputArray (vector<int> &degree_seq);

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void inputApm(vector<tpl> &weight_edges);
    vector<Pair> apmUtil(vector<tpl> &weight_edges);

    //PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
    bool bfsMaxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[], bool visited[]);
    int EdmondsKarp(int src, int dst);

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    void inputRoyFloyd(int dist[][N]);
    void RoyFloydUtil(int dist[][N]);
    void outputRoyFloyd(int dist[][N]);

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    void dfsUtil(int src, int &dst, int count, int &max_count, bool visited[]);
    void dfsDiameter(int src, int &dst,int &max_count, bool visited[]);

    //PROBLEMA CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA: https://infoarena.ro/problema/cuplaj
    bool bfsHopcroftKarp(int pairU[], int pairV[], int dist[]);
    bool dfsHopcroftKarp(int u, int pairU[], int pairV[], int dist[]);

public:
    
    Graph(int nodes_l, int nodes_r, int edges);
    Graph(int nodes, int edges);
    Graph(int nodes);
    Graph(){};

    //PROBLEMA DFS INFOARENA: https://infoarena.ro/problema/dfs
    int connectedComponents();     //determinarea numarului de componente conexe ale grafului

    //PROBLEMA bfs INFORARENA: https://infoarena.ro/problema/bfs
    vector<int> bfs(int start);

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    vector<vector<int>> biconnectedComponents();     //determina componentele biconexe ale unui graf

    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    vector<int> topologicalSort();

    //PROBLEMA HAVEL-HAKIMI
    bool HavelHakimi();

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    vector<Pair> apm();

    //PROBLEMA PADURI DE MULTIMI DISJUNCTE INFOARENA: https://infoarena.ro/problema/disjoint
    void disjoint();

    //PROBLEMA ALGORITMUL LUI DIJKSTRA INFOARENA: https://infoarena.ro/problema/dijkstra
    void Dijkstra();

    //PROBLEMA ALGORITMUL BELLMAN-FORD: https://infoarena.ro/problema/bellmanford
    void BellmanFord();

    //PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
    int maxFlow ();

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    void RoyFloyd();

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    int diameter();

    //PROBLEMA CICLU EULERIAN INFOARENA: https://infoarena.ro/problema/ciclueuler
    vector<int> Euler();
    
    //PROBLEMA CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA: https://infoarena.ro/problema/cuplaj
    vector<Pair> hopcroftKarp();
};

Graph::Graph(int nodes_l, int nodes_r, int edges)
{
    this->nodes_l = nodes_l;
    this->nodes_r = nodes_r;
    this->edges = edges;
}

Graph::Graph(int nodes, int edges)
{
    this->nodes = nodes;
    this->edges = edges;
}

Graph::Graph(int nodes)
{
    this->nodes = nodes;
}

void Graph::dfs(int node, bool visited[])
{
    visited[node] = 1;

    for (int i = 0; i < adj[node].size(); i++)
        if( !visited[adj[node][i]])
            dfs(adj[node][i], visited);
}

void Graph::outputAdj()
{
    for (int node  = 1 ; node <= nodes ; node++)
        for (int i = 0; i < adj[node].size(); i++)
             cout<<adj[node][i]<<" ";
}

void Graph::addEdgesDg(int nodes, int edges)
{
    int node1, node2;

    for(int i = 0 ; i < edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
    }
}

void Graph::addEdgesUg()
{
    int node1, node2;
    for(int i = 0 ; i < edges; i++)
    {
        input >> node1 >> node2;
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }
}

void Graph::addEdgesDgWeight()
{
    int node1, node2, weight;

    for(int i = 0 ; i < edges; i++)
    {
        input >> node1 >> node2 >> weight;
        adj_weight[node1].push_back(make_pair(node2, weight));
    }
}

void Graph::addEdgesDgCapacity()
{
    int node1, node2, capacity;
    for(int i = 0 ; i < edges; i++)
    {
        input >> node1 >> node2 >> capacity;
        adj_capacity[node1].push_back(make_pair(node2, capacity));
    }
}

int Graph::calculateConnectedComponents (bool visited[])
{
    int cc = 0;
    for (int i = 1; i <= nodes; i++)
        if (!visited[i])
        {
            cc++;
            dfs(i, visited);
        }

    return cc;
}

int Graph::connectedComponents()
{
    bool visited[N] = {0};
    
    addEdgesUg();
    return calculateConnectedComponents(visited);
}

vector<int> Graph::bfsUtil (int node, bool visited[])
{
    vector<int> cost;
    queue<int> queue_bfs;

    cost.assign(nodes + 1, -1);

    visited[node] = 1; //marchez nodul curent ca vizitat
    queue_bfs.push(node);
    cost[node] = 0;

    while (!queue_bfs.empty())
    {
        node = queue_bfs.front(); //iau nodul din varful cozii
        queue_bfs.pop();

        for (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
            if ( !visited[adj[node][i]]) //daca sunt nevizitati
            {
                visited[adj[node][i]] = 1;  //ii marchez ca vizitati
                queue_bfs.push(adj[node][i]);   //ii adaug in coada
                cost[adj[node][i]] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
            }
    }
    return cost;
}

vector<int> Graph::bfs(int start)
{
    bool visited[N] = {0};
    
    addEdgesDg(nodes, edges);
    return bfsUtil(start, visited);
}

void Graph::dfsBiconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<Pair> &component_node, int &current, bool visited[])
{
    visited[node] = 1;

    level[node] = level[parent] + 1;
    low_level[node] = level[node];
    int child;

    int dim = adj[node].size();
    for ( int i = 0; i< dim ; i++)
    {
        child = adj[node][i];
        if (child != parent)
        {
            if (visited[child] == true)  //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
            {
                if(level[child] < low_level[node])low_level[node] = level[child];  //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (pt ca avem muchie de intoarcere)
            }
            else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
            {
                component_node.push({node, child});
                dfsBiconnectedComponents(child, node, level, low_level, bcc, component_node, current, visited);

                if (low_level[child] < low_level[node])
                    low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]

                if (low_level[child] >= level[node])        //node este pct de articulatie
                {
                    bcc.push_back({});
                    while( component_node.top().first != node)
                    {
                        bcc.back().push_back(component_node.top().second);
                        component_node.pop();
                    }
                    bcc.back().push_back(component_node.top().second);
                    bcc.back().push_back(component_node.top().first);
                    component_node.pop();
                    current++;
               }
            }
        }
    }
}

vector<vector<int>> Graph::biconnectedComponents()
{
    int level[N] = {0};    //nivelul la care se afla un nod
    int low_level[N] = {0};    //nivelul minim de intoarcere a unui nod
    bool visited[N] = {0};
    stack<pair<int, int>> component_node;
    vector<vector<int>> bcc; //vectorul care stocheaza componentele biconexe
    int current = 0;
    
    addEdgesUg();
    dfsBiconnectedComponents(1,0, level, low_level, bcc, component_node, current, visited);
    
    return bcc;
}

void Graph::calculateIndegree (int indegree[])
{
    int node1, node2;
    memset(indegree, 0, nodes);

    for(int i = 0 ; i < edges; i++)
    {
        input>>node1>>node2;
        adj[node1].push_back(node2);
        indegree[node2]++;
    }
}

vector<int> Graph::topSort(int indegree[], queue<int> queue_ts)
{
    vector<int> sortedVector;
    int dim = nodes;
    for (int i = 1; i <= dim ; i++)  //adaugam in coada doar nodurile care au gradul 0
    {
        if (indegree[i] == 0)
            queue_ts.push(i);
    }

    while (!queue_ts.empty()) //cat timp coada nu este goala, extragem varful, scadem gradele nodurilor adiacente cu varful si adaugam in coada acele noduri care au gradul interior 0
    {
        int node = queue_ts.front();
        queue_ts.pop();

        for (int i = 0; i < adj[node].size(); i++)
        {
            int adj_node = adj[node][i];
            indegree[adj_node]--;
            if (!indegree[adj_node])
                queue_ts.push(adj_node);
        }
        sortedVector.push_back(node);
    }
    return sortedVector;
}

vector<int> Graph::topologicalSort()
{
    queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
    int indegree[N] ; //vectorul care retine gradul interior al fiecarui nod

    calculateIndegree(indegree);
    return topSort(indegree, queue_ts);
}

bool Graph::graphExists (vector<int> degree_seq)
{
    while (1)
    {
        sort(degree_seq.begin(), degree_seq.end(), greater<>());
        cout<<degree_seq[0]<<" ";
        if (degree_seq[0] == 0)  //daca toate elementele ramase sunt 0, atunci se poate construi un graf
            return true;

        int top = degree_seq[0];
        degree_seq.erase(degree_seq.begin());

        if (top > degree_seq.size()) // daca valoarea primului element este mare decat numarul de elemente ramase, nu putem construi un astfel de graf
            return false;

        for (int i = 0 ; i < degree_seq.size(); i++) //dupa eliminarea primului element, scadem gradul "nodurilor" ramase
        {
            degree_seq[i]--;
            if(degree_seq[i] < 0)  //daca apar numere negative, nu putem sa construim un graf
                return false;
        }
    }
}

void Graph::inputArray (vector<int> &degree_seq)
{
    int n;
    input>>n;

    for (int i = 0; i < n; i++)
    {
        int val;
        input>>val;
        degree_seq.push_back(val);
    }
}

bool Graph::HavelHakimi()
{
    vector<int> degree_seq; //vectorul care contine gradele unui posibil graf

    inputArray(degree_seq);
    return graphExists(degree_seq);
}

bool Graph::sortByThird (const tpl &a, const tpl&b)
{
    return (get<2>(a) < get<2>(b));
}

void Graph::inputApm(vector<tpl> &weight_edges)
{
    for (int i = 0 ; i < edges; i++)
    {
        int n1, n2, weight;
        input >> n1 >> n2 >> weight;
        weight_edges.push_back(make_tuple(n1,n2,weight));
    }
}

vector<Pair> Graph::apmUtil(vector<tpl> &weight_edges)
{
    int height[N] = {0};
    int father[N] = {0};
    sort(weight_edges.begin(), weight_edges.end(), sortByThird);   //sortam vectorul crescator in functie de cost

    DisjointSets djs(nodes);
    djs.initialization(nodes);     //consideram ca fiecare nod reprezinta un subarbore

    int weight = 0;     //costul arborelui
    int ctr = 0;        //numarul de muchii ale APM intr-un anumit moment
    vector<Pair> apm;
    for (int i = 0; i < edges; i++)
    {
        int n1 = get<0>(weight_edges[i]);       //la fiecare iteratie alegem muchia cu cost minim
        int n2 = get<1>(weight_edges[i]);

        int r1 = djs.reprezentative(n1, father);        //verificam reprezentantii nodurilor incidente acestei muchii
        int r2 = djs.reprezentative(n2, father);

        if (r1 != r2)       //daca avem reprezentanti diferiti, subarborii din care fac parte nodurile se reunesc; altfe,l, ignoram muchia, deoarece ar genera un ciclu in APM
        {
            apm.push_back(make_pair(n1, n2));
            ctr++;
            weight += get<2>(weight_edges[i]);
            djs.reunite(n1, n2, height, father);

            if  (ctr == nodes - 1)      //un arbore poate avea maximum n-1 muchii intre noduri; astfel, daca am gasit n-1 muchii putem opri cautarea
                break;
        }
    }

    output<<weight<<"\n";
    output<<nodes - 1<<"\n";
    return apm;
}

vector<Pair> Graph::apm()
{
    vector<tpl> weight_edges;
    
    inputApm(weight_edges);
    return apmUtil(weight_edges);
}

void Graph::disjoint()
{
    int height[N] = {0};
    int father[N] = {0};

    int sets, tasks;
    input >> sets >> tasks;

    DisjointSets djs(nodes);
    djs.initialization(nodes);

    for (int i = 0; i < tasks; i++)
    {
        int task, x, y;
        input >> task >> x >> y;

        if (task == 1)
            djs.reunite(x, y, height, father);
        else
        {
            int r1 = djs.reprezentative(x, father);
            int r2 = djs.reprezentative(y, father);
            
            if(r1 != r2)
                output<<"NU\n";
            else output<<"DA\n";
        }
    }
}

void Graph::Dijkstra()
{
    int dist[N];       //vectorul care retine distanta minima de la nodul de start la celelalte noduri
    int start = 1;
    priority_queue<Pair, vector<Pair>, greater<Pair>> queue_adj;   //coada in care retinem nodurile adiacente si costurile muchiilor de adiacenta ale nodului vizitat curent pentru a avea ordinea parcurgerii
                                                                //vom retine mai intai costul si apoi nodul adiacent pentru a putea obtine cu usurinta la fiecare iteratie nodul care are muchia asociata de cost minim

    for (int i = 1; i <= nodes; i++)
        dist[i] = INF;

    queue_adj.push(make_pair(0, start));   //pentru nodul de start avem costul 0 pentru a ajunge la el
    dist[start] = 0;

    while (!queue_adj.empty()) {
        int node = get<1>(queue_adj.top());
        queue_adj.pop();

        for (int i = 0; i < adj_weight[node].size(); i++)       //pentru toate nodurile adiacente ale lui node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])      //verificam daca pentru nodurile adiacente gasim un drum mai scurt prin node decat cele parcurse deja
            {
                dist[child] = dist[node] + weight;
                queue_adj.push(make_pair(dist[child], child));
        
            }
        }
    }

    for (int i = 2; i <= nodes; i++)
        if (dist[i] == INF)
            output<<"0 ";
        else output<<dist[i]<<" ";
}

void Graph::BellmanFord()
{
    int dist[N];  //vectorul care retine distanta minima de la nodul de start(1) la toate celelalte noduri
    int len[N] = {0};  //vectorul care memoreaza lungimea unui drum de la sursa la un alt nod
    queue<int> queue_bf;        //coada care memoreaza nodurile ale caror distanta minima s-a modificat
    int start = 1;
    bool cycle = false;        //presupunem ca in graf nu exista cicluri negative

    for (int i = 1; i <= nodes; i++)
        dist[i] = INF;

    dist[start] = 0;        //pentru nodul 1 avem costul 0 pentru a ajunge la el
    queue_bf.push(start);

    while (!queue_bf.empty() && !cycle)
    {
        int node = queue_bf.front();
        queue_bf.pop();

        for (int i = 0; i < adj_weight[node].size(); i++)  //pentru toate nodurile adiacente cu node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])      //verificam daca gasim un drum mai scurt decat cel parcurs deja
            {
                len[child] = len[node] + 1;
                if (len[child] == nodes)   //daca obtinem o lungime mai mare sau egala cu n, inseamna ca in graf exista un ciclu negativ
                {
                    cycle = true;
                    break;
                }
                dist[child] = dist[node] + weight;
                queue_bf.push(child);
            }
        }
    }

    if (cycle)
        output<<"Ciclu negativ!";
    else
        for (int i = 2; i <= nodes; i++)
            output<<dist[i]<<" ";
}

bool Graph::bfsMaxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[], bool visited[])
{
    memset(visited, false, sizeof(visited));

    queue<int> q;
    q.push(src);
    visited[src] = true;        //marcam nodul curent ca vizitat
    parent[src] = 0;

    while (!q.empty())
    {
        int node = q.front();       //luam primul element din coada
        q.pop();
        
        for (int i = 0 ; i < adj_capacity[node].size(); i++)        //parcurg toate nodurile adiacente cu nodul curent
        {
            int j = get<0>(adj_capacity[node][i]);
            if (!visited[j] && residualGraph[node][j] > 0)
            {
                if (j == dst)       //daca am gasit un drum de la sursa la destinatie, ne oprim cu bfsMaxFlow
                {
                    parent[j] = node;
                    return true;
                }
                q.push(j);
                parent[j] = node;
                visited[j] = true;
            }
        }
    }
    return false;
}

int Graph::EdmondsKarp(int src, int dst)
{
    vector<vector<int>> residualGraph;        //cream un graf rezidual pe care il initializam cu valorile capacitatilor din graful original
                                    //residualGraph[i][j] -> capacitatea arcului de la i la j, daca acesta exista
    bool visited[N] = {0};
    int parent[nodes + 1];         //vectoul folosit pentru a memora drumul de la sursa la destinatie
    int max_flow = 0;       //initial nu avem niciun flux
    
    residualGraph.resize(nodes + 1, vector<int> (nodes + 1, 0));
    for (int i = 1; i <= nodes; i++)
        for (int j = 0; j < adj_capacity[i].size(); j++)
        {
            int col = get<0>(adj_capacity[i][j]);
            residualGraph[i][col] = get<1>(adj_capacity[i][j]);
        }

    while (bfsMaxFlow(src, dst, residualGraph, parent, visited)) {      //cat timp avem drum de la sursa la destinatie
        //cautam capacitatea reziduala minima a fiecarui arc de-a lungul drumului gasit de bfs
        int path_flow = INT_MAX;
        for (int i = dst ; i != src; i = parent[i])
        {
            int node = parent[i];
            path_flow = min(path_flow, residualGraph[node][i]);
        }
        
        //modificam valorile reziduale ale arcelor directe si inverse care se afla pe drumul gasit de bfs
        for (int i = dst ; i != src; i = parent[i])
        {
            int node = parent[i];
            residualGraph[node][i] -= path_flow;
            residualGraph[i][node] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int Graph::maxFlow()
{
    addEdgesDgCapacity();
    return EdmondsKarp(1, nodes);
}

void Graph::RoyFloydUtil(int dist[][N])
{
    int n = nodes;
    for (int k = 1; k <= n; k++)       //consideram pe rand fiecare nod ca fiind intermediar
        for (int i = 1; i <= n; i++)       //consideram pe rand ca fiecare nod este sursa
            for (int j = 1; j <= n; j++)       //consideram pe rand fiecare nod ca fiind destinatie
                if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) {     //modificam distanta
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
}

void Graph::outputRoyFloyd(int dist[][N])
{
    for (int i = 1; i <= nodes; i++)
    {
        for (int j = 1; j <= nodes; j++)
            if (dist[i][j] == INF || i == j)
                output<<"0 ";
            else
                output<<dist[i][j]<<" ";
        output<<"\n";
    }
}

void Graph::inputRoyFloyd(int dist[][N])
{
    for (int  i = 1; i <= nodes; i++)
        for (int j = 1; j <= nodes; j++)
    {
        input>>dist[i][j];
        if (!dist[i][j]) dist[i][j] = INF;
    }
}

void Graph::RoyFloyd()
{
    int dist[N][N];      // dist este matricea rezultat care contine drumul minim intre toate perechile de noduri
    inputRoyFloyd(dist);
    RoyFloydUtil(dist);
    outputRoyFloyd(dist);
}

void Graph::dfsUtil(int src, int &dst, int count, int &max_count, bool visited[])
{
    visited[src] = true;
    count++;
    for (int i = 0; i < adj[src].size(); i++)
    {
        if (!visited[adj[src][i]]){
            if (count >= max_count)
            {
                max_count = count;
                dst = adj[src][i];
            }
            dfsUtil(adj[src][i], dst, count, max_count, visited);
        }
    }
}

void Graph::dfsDiameter(int src, int &dst, int &max_count, bool visited[])
{
    int count = 0;
    for (int i = 1 ; i <= nodes; i++)
        visited[i] = false;

    dfsUtil(src, dst, count + 1, max_count, visited);
}

int Graph::diameter()
{
    addEdgesUg();
    int max_count = INT_MIN;
    int src, dst;
    bool visited[N] = {0};

    dfsDiameter(1, dst, max_count, visited);
    dfsDiameter(dst, src, max_count, visited);

    return max_count;
}

vector<int>Graph::Euler()
{
//    vector<tpl> edges[N];       //vector of adjacent nodes; for each edge, it stores a unique code for easier identification of each edge
//    bool eliminated[M] = {false};       //if we eliminate an edge, eliminated[edge_code] becomes true
//    stack<int> stack_euler;
//    vector<int> eulerCircuit;
//
//    int nodes, edges;
//    input >> nodes >> edges;
//
//    for (int i = 0 ; i < edges ; i++)
//    {
//        int x, y;
//        input>>x>>y;
//        edges[x].push_back(make_tuple(y,i));
//        edges[y].push_back(make_tuple(x,i));
//    }
//
//    for (int i = 1 ; i <= nodes ; i++)
//    {
//        if (edges[i].size() % 2)        //if the graph contains odd vertices, then it can't have an euler circuit
//        {
//            eulerCircuit.push_back(-1);
//            return eulerCircuit;
//        }
//    }
//
//    stack_euler.push(1);        //we simulate the recursion using a stack
//    while (!stack_euler.empty())
//    {
//        int node = stack_euler.top();
//        if (!edges[node].empty())       //if the current node still has adjacent nodes
//        {
//            tpl t = edges[node].back();
//            edges[node].pop_back();
//
//            int adj_node = get<0>(t);
//            int edge_code = get<1>(t);
//
//            if (!eliminated[edge_code])
//            {
//                eliminated[edge_code] = true;       //we eliminate the edge
//                stack_euler.push(adj_node);         //and continue the recursion from the adjacent node
//            }
//        }
//        else    //the node can be added to the euler circuit
//        {
//            stack_euler.pop();
//            eulerCircuit.push_back(node);
//        }
//    }
//    eulerCircuit.pop_back();
//
//    return eulerCircuit;
    return {0};
}

bool Graph::bfsHopcroftKarp(int pairU[], int pairV[], int dist[])
{
    queue<int> q;
    
    for (int u = 1 ; u <= nodes_l ; u++)        //take the first layer of vertices
    {
        if (pairU[u] == NIL)        //if there is a free vertex, add it to queue
        {
            dist[u] = 0;        //u is not matched
            q.push(u);
        }
        else
        {
            dist[u] = INF;      //else set distance INF so that this vertex is considered next time
        }
    }
    
    dist[NIL] = INF;
    
    while (!q.empty())      //while queue contains vertices from the left side only
    {
        int u = q.front();      //dequeue a vertex
        q.pop();
        
        if (dist[u] < dist[NIL])        //if current node is not NIL and can provide a sorther path to NIL
        {
            for (int i = 0 ; i < adj[u].size() ; i++)       //get all adjacent vertices of current node
            {
                int v = adj[u][i];
                
                if (dist[pairV[v]] == INF)
                {
                    dist[pairV[v]] = dist[u] + 1;
                    q.push(pairV[v]);
                }
            }
        }
    }
    //if we could come back to NIL using alternating path of distinct vertices then there is an augmenting path
    return (dist[NIL] != INF);
}

bool Graph::dfsHopcroftKarp(int u, int pairU[], int pairV[], int dist[])
{
    if (u != NIL)
    {
        for (int i = 0 ; i < adj[u].size() ; i++)       //get all adjacent vertices of current node
        {
            int v = adj[u][i];
            
            if (dist[pairV[v]] == dist[u] + 1)      //follow the distances set by bfs
            {
                if (dfsHopcroftKarp(pairV[v], pairU, pairV, dist))
                {
                    pairV[v] = u;
                    pairU[u] = v;
                    return true;
                }
            }
        }
        
        //if there is no augmenting path beginning with u
        dist[u] = INF;
        return false;
    }
    return true;
}

vector<Pair> Graph::hopcroftKarp()
{
    /*Free Node or Vertex -> Given a matching M, a node that is not part of matching is called free node. Initially all vertices are free.
     
     Matching and Not-Matching edges -> Given a matching M, edges that are part of matching are called Matching edges and edges that are not part of M (or connect free nodes) are called Not-Matching edges.

     Alternating Paths -> Given a matching M, an alternating path is a path in which the edges belong alternatively to the matching and not matching. All single edges paths are alternating paths.

     Augmenting path -> Given a matching M, an augmenting path is an alternating path that starts from and ends on free vertices. All single edge paths that start and end with free vertices are augmenting paths.
     */
    
    
    for (int i = 0 ; i < edges ; i++)
    {
        int x, y;
        input >> x >> y;
        adj[x].push_back(y);
    }
    
    int pairU[nodes_l + 1];       //stores pair of u in matching where u is a vertex on left side of bipartite graph
    int pairV[nodes_r + 1];       //stores pair of v in matching where v is a vertex on right side of bipartite graph
    int dist[nodes_l + 1];        //stores distance of left side vertices
    
    for (int i = 0 ; i <= nodes_l ; i++)
        pairU[i] = NIL;
    for (int j = 0; j <= nodes_r; j++)
        pairV[j] = NIL;
    
    int result = 0;
    vector<Pair> result_nodes;
    result_nodes.push_back(make_pair(0,0));        //contains the number of edges and the edges that form the maximum matching
    
    while (bfsHopcroftKarp(pairU, pairV, dist) == true)        //keep updating the result while we have an augmenting paht
    {
        for (int u = 1 ; u <= nodes_l ; u++)        //find a free vertex
        {
            if (pairU[u] == NIL && dfsHopcroftKarp(u, pairU, pairV, dist) == true)     //if the current vertex is free and there is an augmenting path from it
            {
                get<0>(result_nodes[0]) = ++result;
                result_nodes.push_back(make_pair(u, pairU[u]));
            }
        }
    }
    
    return result_nodes;
}

int main(int argc, const char * argv[])
{
    Graph g;
    g.disjoint();
}