//
//  main.cpp
//  Diametrul unui arbore
//
//  Created by Mara Dascalu on 29/11/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 N  100010
typedef std::tuple<int, int> tpl;

using namespace std;

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

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

public:

    void set_no_nodes(int nr) { no_nodes = nr;}
    int get_no_nodes() { return no_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
};

void DisjointSets::initialization(int no_node)
{
    set_no_nodes(no_nodes);

    reprez.push_back(0);
    for (int i = 1 ; i <= no_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;
    vector<int> adj[N] ;
    vector<tuple<int,int>> adj_weight[N];
    vector<tuple<int,int>> adj_capacity[N];
    bool visited[N] = {0};

//    void sccUtil (int node, int disc[], int low[], stack<int> *st, bool stackMember[]);       //functia auxiliara pentru determinarea componentelor tare conexe
    void DFS(int node);     //parcurgerea DFS a grafului
    void afis_adj(int node);       //afisarea vectorului de vectori de adiacenta a nodurilor
    static bool sortByTh (const tuple<int,int,int> &a, const tuple<int,int,int>&b);    //sorteaza vectorul de tupluri coare contine si costul muchiilor dupa al treilea parametru (cost)

public:

    void set_no_nodes(int n) {nodes = n;}
    int get_no_nodes() {return nodes;}
    void set_no_edges(int n) {edges = n;}
    int get_no_edges() {return edges;}

    void addEdge_dg (int no_nodes, int no_edges);
    void addEdge_ug ();
    void addEdge_dg_weight();
    void addEdge_dg_capacity();

    //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
    void BFS (int node);    //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 DFS(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current);     // DFS auxiliar pentru determinarea componentelor biconexe
    void biconnectedComponents();     //determina componentele biconexe ale unui graf

    //PROBLEMA COMPONENTE TARE CONEXE INFOARENA: https://infoarena.ro/problema/ctc
//    void scc();      //determinarea componentelor tare conexe ale unui graf

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

    //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);
    void Havel_Hakimi();

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void inputAPM(vector<tuple<int,int,int>> &weight_edges);
    void APMUtil(vector<tuple<int,int,int>> &weight_edges);
    void 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 Bellman_Ford();

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

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    void inputRoy_Floyd(int dist[][N]);
    void Roy_FloydUtil(int dist[][N]);
    void outputRoy_Floyd(int dist[][N]);
    void Roy_Floyd();

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    void dfsUtil(int src, int &dst, int count, int &max_count);
    void dfs_diameter(int src, int &dst,int &max_count);
    int diameter();
}g;

//void Graph::sccUtil (int node, int disc[], int low[], stack<int> *st, bool stackMember[])
//    {
//        static int time = 0;
//        int current =0;
//
//        //initializare disc si low pentru nodul curent
//        disc[node] = low[node] = time++;
//        st->push(node);
//        stackMember[node] = true;
//
//        //parcurgem toti vecinii lui node
//        for (int i = 0; i < adj[node].size(); i++)
//        {
//            int adj_node = adj[node][i];
//
//            if (!disc[adj_node])  //daca vecinul nu a fost vizitat inca
//            {
//                sccUtil(adj_node, disc, low, st, stackMember);
//
//                low[node] = min(low[node], low[adj_node]); //verificam daca subarborele care are drep radacina adj_node are un drum catre un stramos al lui node
//            }
//            else if (stackMember)
//            {
//                low[node] = min(low[node], disc[adj_node]);  //facem update daca avem muchie de intoarcere
//            }
//        }

void Graph::DFS(int node)
{
    visited[node] = 1;
    output<<node<<" ";

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

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

void Graph::addEdge_dg (int no_nodes, int no_edges)
{
//       int no_nodes, no_edges;
//       input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2;

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

void Graph::addEdge_ug ()
{
    int no_nodes;
    input>>no_nodes;
    set_no_nodes(no_nodes);

    int node1, node2;

    while (input>>node1>>node2) {
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }
}

void Graph::addEdge_dg_weight()
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2, weight;

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

void Graph::addEdge_dg_capacity()
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    int node1, node2, capacity;
    for(int i = 0 ; i < no_edges; i++)
    {
        input>>node1>>node2>>capacity;
        adj_capacity[node1].push_back(make_tuple(node2, capacity));
    }
}

int Graph::connectedComponents ()
{
    int cc = 0;
    for (int i = 1; i <= get_no_nodes(); i++)
        if (!visited[i])
        {
            cc++;
            DFS(i);
        }
    return cc;
}

void Graph::BFS (int node)
{
    int cost[100010];
    queue<int> queue_bfs;

    memset(cost,  -1, sizeof(cost));

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

    for (int i = 1; i <= get_no_nodes(); i++)
        output<<cost[i]<<" ";
}

void Graph::DFS(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current)
{
    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});
                DFS(child, node, level, low_level, bcc, component_node, current);

                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])        //nodul k 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++;
               }
            }
        }
    }
}

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

    DFS(1,0, level, low_level, bcc, component_node, current);

    output<<current << "\n";
    for (int i =0 ; i <= current; i++)
        {
            for (int j = bcc[i].size() - 1; j >= 0; j--)
                if(bcc[i][j])
                    output<<bcc[i][j]<<" ";
            output<<"\n";
        }
}

//void Graph::scc()
//    {
//        int dim = get_no_nodes();
//        int *disc = new int[dim]; //memoreaza timpul de descoperire al fiecarui nod
//        int *low = new int[dim]; //memoreaza timpul de descoperire minim care poate fi accesat din subarborele care are radacina in fiecare nod
//        bool *stackMember = new bool[dim]; //pentru verificarea mai rapida daca un nod este sau nu in stiva
//        stack<int> *st = new stack<int>();  //pentru stocarea compo\ conexe
//
//        for (int i = 0; i < dim ; i++)
//        {
//            disc[i] = low[i] = 0;
//            stackMember[i] = false;
//        }
//
//        //apelam recursiv sccUtil pentru gasirea comp tare conexe
//        for (int i = 1; i <= dim; i++)
//            if(!disc[i])
//                sccUtil(i, disc, low, st, stackMember);
//    }

//    void output_scc ()
//    {
//        output<<current<<"\n";
//        for (int i = current - 1; i >= 0 ; i--)
//        {
//            for (int j = 0; j < vec_scc[i].size(); j++)
//                output<<vec_scc[i][j]<<" ";
//            output<<"\n";
//        }
//    }

void Graph::calculateIndegree (int indegree[])
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);

    int node1, node2;
    memset(indegree, 0, no_nodes);

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

void Graph::topSort(int indegree[], queue<int> queue_ts)
{
    int dim = get_no_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);
        }
        cout<<node<<" ";
    }
}

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

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

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

    inputArray(degree_seq);
    output<<graphExists(degree_seq);
}

bool Graph::sortByTh (const tuple<int,int,int> &a, const tuple<int,int,int>&b)
{
    return (get<2>(a) < get<2>(b));
}

void Graph::inputAPM(vector<tuple<int,int,int>> &weight_edges)
{
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_nodes(no_nodes);
    set_no_edges(no_edges);

    for (int i = 0 ; i < no_edges; i++)
    {
        int n1, n2, weight;
        input>>n1>>n2>>weight;
        weight_edges.push_back(make_tuple(n1,n2,weight));
    }
}

void Graph::APMUtil(vector<tuple<int,int,int>> &weight_edges)
{
//    sort(weight_edges.begin(), weight_edges.end(), sortByTh);   //sortam vectorul crescator in functie de cost
//
//    DisjointSets djs;
//    djs.initialization(get_no_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<tuple<int,int>> apm;
//    for (int i = 0; i < get_no_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);        //verificam reprezentantii nodurilor incidente acestei muchii
//        int r2 = djs.reprezentative(n2);
//
//        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_tuple(n1, n2));
//            ctr++;
//            weight += get<2>(weight_edges[i]);
//            djs.reunite(n1, n2);
//
//            if  (ctr == get_no_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<<get_no_nodes() - 1<<"\n";
//    for (int i = 0; i < apm.size(); i++)
//        output<<get<0>(apm[i])<<" "<<get<1>(apm[i])<<"\n";
}

void Graph::APM()
{
    vector<tuple<int,int,int>> weight_edges;

    inputAPM(weight_edges);
    APMUtil(weight_edges);

}

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

    int no_sets, no_tasks;
    input>>no_sets>>no_tasks;

    DisjointSets djs;

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

        if (no_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[100010];       //vectorul care retine distanta minima de la nodul de start la celelalte noduri
    int start = 1;
    priority_queue<tpl, vector<tpl>, greater<tpl>> 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 <= get_no_nodes(); i++)
        dist[i] = INF;

    queue_adj.push(make_tuple(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_tuple(dist[child], child));
            }
        }
    }

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

void Graph::Bellman_Ford()
{
    int dist[100010];  //vectorul care retine distanta minima de la nodul de start(1) la toate celelalte noduri
    int len[100010] = {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 <= get_no_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] == get_no_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 <= get_no_nodes(); i++)
            output<<dist[i]<<" ";
}

bool Graph::bfs_maxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[])
{
    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 bfs_maxFlow
                {
                    parent[j] = node;
                    return true;
                }
                q.push(j);
                parent[j] = node;
                visited[j] = true;
            }
        }
    }
    return false;
}

int Graph::Edmonds_Karp(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
    int parent[get_no_nodes() + 1];         //vectoul folosit pentru a memora drumul de la sursa la destinatie
    int max_flow = 0;       //initial nu avem niciun flux
    residualGraph.resize(get_no_nodes() + 1, vector<int> (get_no_nodes() + 1, 0));
    for (int i = 1; i <= get_no_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 (bfs_maxFlow(src, dst, residualGraph, parent)) {      //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()
{
    addEdge_dg_capacity();
    return Edmonds_Karp(1, get_no_nodes());
}

void Graph::Roy_FloydUtil(int dist[][N])
{
    int n = get_no_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::outputRoy_Floyd(int dist[][N])
{
    for (int i = 1; i <= get_no_nodes(); i++)
    {
        for (int j = 1; j <= get_no_nodes(); j++)
            if (dist[i][j] == INF || i == j)
                output<<"0 ";
            else
                output<<dist[i][j]<<" ";
        output<<"\n";
    }
}

void Graph::inputRoy_Floyd(int dist[][N])
{
    int no_nodes;
    input>>no_nodes;
    set_no_nodes(no_nodes);

    for (int  i = 1; i <= no_nodes; i++)
        for (int j = 1; j <= no_nodes; j++)
    {
        input>>dist[i][j];
        if (!dist[i][j]) dist[i][j] = INF;
    }
}

void Graph::Roy_Floyd()
{
    int dist[N][N];      // dist este matricea rezultat care contine drumul minim intre toate perechile de noduri
    inputRoy_Floyd(dist);
    Roy_FloydUtil(dist);
    outputRoy_Floyd(dist);
}

void Graph::dfsUtil(int src, int &dst, int count, int &max_count)
{
    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);
        }
    }
}

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

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

int Graph::diameter()
{
    addEdge_ug();
    int max_count = INT_MIN;
    int src, dst;

    dfs_diameter(1, dst, max_count);
    dfs_diameter(dst, src, max_count);

    return max_count;
}

int main(int argc, const char * argv[])
{
    output << g.maxFlow() << "\n";
    //output<<g.diameter()<<"\n";
}