#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <sys/resource.h> // posix header

using namespace std;

struct edge
{
    int node;
    int neighbour;
    long cost;
    int capacity;
};

class Graph {
    int nrNodes; //number of nodes
    vector<vector<edge>> edges; // list of connections between nodes
public:
    Graph(int _nrNodes);
    int getNrNodes() const;
    void setEdge(int node, int neighbour, int cost=0, int capacity=0);
    void printEdges() const;
    const vector<edge>& getNeighbours(int node);
    virtual ~Graph() = default;

    int nrConnectedComponents();

    vector<int> getDistancesBFS(const int& start);
    vector<bool> DFS(const int& start);
    vector<int> PrimMST(int& costMST);
    vector<int> Dijkstra(const int& start = 0);
    vector<int> BellmanFord(const int& start = 0);
    static void disjointSets(int op, int node1, int node2,
                      vector<bool>& sameGroup, vector<int>& root);
    vector<vector<int>> getMinCostMatrix();
    int getTreeDiameter(const int& start);
    int getMinSalesmanCost(const int& start, vector<int>& costs);

private:
    void DFS(int node, vector<bool>& visited); //helper for nrConnectedComponents
    static int findGroup(int node, vector<int>& root); //with path compression
    static void unifyGroups(int node1, int node2, vector<int>& root);
};
//--------Graph.cpp--------------------------------------------------------------------------------------


Graph::Graph(int _nrNodes)
{
    this -> nrNodes = _nrNodes;
    this -> edges.resize(_nrNodes+1);
    /*
     * Nodes start at 1, but index starts at 0
     */
}


int Graph::getNrNodes() const
{
    return this -> nrNodes;
}

void Graph::setEdge(int node, int neighbour, int cost, int capacity)
{
    struct edge tmp{};
    tmp.neighbour = neighbour;
    tmp.cost = cost;
    tmp.capacity = capacity;
    this -> edges[node].push_back(tmp);
}


const vector<edge>& Graph::getNeighbours(int node)
{
    return this -> edges[node];
}


int Graph::nrConnectedComponents()
{
    int ans = 0;
    vector<bool> visited(this -> nrNodes+1, false);
    for(int i = 1 ; i <= this -> nrNodes; i++)
        if(!visited[i])
        {
            DFS(i, visited);
            ++ans;
        }
    return ans;
}


vector<int> Graph::getDistancesBFS(const int& start)
{
    vector<int>distances(this->nrNodes + 1, -1);
    distances[start] = 0;

    queue<int>toBeVisited;
    toBeVisited.push(start);

    while(!toBeVisited.empty())
    {
        int x = toBeVisited.front();
        toBeVisited.pop();

        for(auto& it: this->edges[x])
            if(distances[it.neighbour] == -1)
            {
                distances[it.neighbour] = distances[x] + 1;
                toBeVisited.push(it.neighbour);
            }

    }

    return distances;
}

vector<bool> Graph::DFS(const int &start)
{
    vector<bool> visited(this->nrNodes + 1, false);
    DFS(start, visited);

    return visited;
}


vector<int> Graph::PrimMST(int& costMST)
{
    vector<int> parent(this->nrNodes+1, 0);
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    vector<bool> inMST(this -> nrNodes+1, false);
    priority_queue<pair<int, int>,vector<pair<int, int>> ,greater<>>edgePQ;
    minCost[1] = 0;
    edgePQ.push(make_pair(0, 1)); //cost has to be first for greater<> to work

    while(!edgePQ.empty())
    {
        int currCost = edgePQ.top().first;
        int node = edgePQ.top().second;
        edgePQ.pop();

        if(inMST[node])
            continue;

        inMST[node] = true;
        costMST += currCost;

        for(auto& it: edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(!inMST[neighbour] && minCost[neighbour] > cost)
            {
               minCost[neighbour] = cost;
               parent[neighbour] = node;
               edgePQ.push(make_pair(minCost[neighbour], neighbour));
            }
        }
    }
    return parent;
}


void Graph::DFS(int start, vector<bool>& visited)
{
    visited[start] = true;
    for(auto &it: this ->edges[start])
    {
        int neighbour = it.neighbour;
        if(!visited[neighbour])
        {
            visited[neighbour] = true;
            DFS(neighbour, visited);
        }
    }
}


void Graph::printEdges() const
{
  for(int i = 1; i <= this->getNrNodes(); i++)
  {
      cout << i<< ": ";
      for(auto &it: edges[i])
          cout << it.neighbour<< " ";
      cout << "\n";
  }
}


vector<int> Graph::Dijkstra(const int& start)
{
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    vector<bool> extracted(this -> nrNodes+1, false);
    priority_queue<pair<int, int>,vector<pair<int, int>> ,greater<>>edgePQ;
    minCost[start] = 0;
    edgePQ.push(make_pair(0, start)); //cost has to be first for greater<> to work

    while(!edgePQ.empty())
    {
        int node = edgePQ.top().second;
        edgePQ.pop();

        if(extracted[node])
            continue;

        extracted[node] = true;

        for(auto& it: edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(minCost[node] + cost < minCost[neighbour])
            {
                minCost[neighbour] = minCost[node] + cost;
                edgePQ.push(make_pair(minCost[neighbour], neighbour));
            }
        }
    }
    return minCost;
}


vector<int> Graph::BellmanFord(const int& start)
{
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    queue<int> activeNodes;
    vector<bool> inQueue(this ->nrNodes+1, false);
    vector<int> nodeOptimizations(this->nrNodes+1, 0);
    minCost[start] = 0;
    activeNodes.push(start);
    inQueue[start] = true;
    nodeOptimizations[start] = 1;

    while(!activeNodes.empty())
    {
        int node = activeNodes.front();
        activeNodes.pop();
        inQueue[node] = false;

        for(auto& it: this -> edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(minCost[node] + cost < minCost[neighbour])
            {
                minCost[neighbour] = minCost[node] + cost;
                if(!inQueue[neighbour])
                {
                    activeNodes.push(neighbour);
                    inQueue[neighbour] = true;
                    nodeOptimizations[neighbour]++;
                }
                if(nodeOptimizations[neighbour] >= this->nrNodes)
                    return {-1};

            }
        }
    }

    return minCost;
}


void Graph::disjointSets(int op, int node1, int node2,
                         vector<bool>& sameGroup, vector<int>& root)
{
    if(op == 1)
        unifyGroups(node1, node2, root);
    else
    {
        int group1 = findGroup(node1, root);
        int group2 = findGroup(node2, root);
        sameGroup.push_back(group1 == group2);
    }


}


int Graph::findGroup(int node, vector<int>& root)
{
    int temp = node;
    while(temp != root[temp])
        temp = root[temp];

    while(node != temp) //temp is root now
    {
        int next = root[node];
        root[node] = temp;
        node = next;
    }
    return temp;
}


void Graph::unifyGroups(int node1, int node2, vector<int>& root)
{
    int root1 = findGroup(node1, root);
    int root2 = findGroup(node2, root);
    if(root1 == root2)
        return; // nodes are in the same group
    else
        root[root1] = root2;
}


vector<vector<int>> Graph::getMinCostMatrix()
{
    int n = this -> nrNodes;
    vector<vector<int>> dp;
    dp.resize(n+1);
    int infinity = INT_MAX / 4; //avoid overflow

    for(int i = 1; i <= n; i++)
    {   dp[i].resize(n+1);
        for (int j = 1; j <= n; j++)
            if (i != j && this->edges[i][j-1].cost == 0)
                dp[i][j] = infinity;
            else
                dp[i][j] = this->edges[i][j-1].cost;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(dp[i][k] + dp[k][j] < dp[i][j])
                    dp[i][j] = dp[i][k] + dp[k][j];

    return dp;
}


int Graph::getTreeDiameter(const int &start)
{
    int maxDist = -1;
    int endpoint;
    vector<int> dist = getDistancesBFS(start);

    for(int i = 1; i <= this -> nrNodes; i++)
        if(dist[i] > maxDist)
        {
            maxDist = dist[i];
            endpoint = i;
        }

    dist = getDistancesBFS(endpoint);
    maxDist = -1;

    for(int i = 1; i <= this -> nrNodes; i++)
        if(dist[i] > maxDist)
            maxDist = dist[i];

    return maxDist + 1;
    // +1 bc the diameter is the max no of nodes on te longest chain in the tree
   // that is the no of edges + 1
}


int Graph::getMinSalesmanCost(const int &start, vector<int>& costs)
{
    int n = this -> nrNodes;
    vector<vector<int>> dp(n);
    for(int i = 0; i < n; i++)
    {
        dp[i].resize(1 << n);
        for(int j = 0; j < (1 << n); j++)
            dp[i][j] = INT_MAX;
    }
    dp[start][1] = 0;

    for(int mask = 0; mask < (1 << n); mask++)
    {
        for(int node = 0; node < n; node++)
        {
            if(dp[node][mask] == INT_MAX)
                continue;

            for(auto& edge: edges[node])
            {
                int neighbour = edge.neighbour;
                int cost = edge.cost;

                if(mask & (1 << neighbour))
                    continue; // neighbour already on this path

                int new_mask = mask | (1 << neighbour);
                if(dp[neighbour][new_mask] > dp[node][mask] + cost)
                    dp[neighbour][new_mask] = dp[node][mask] + cost;
            }
        }
    }
    int ans = INT_MAX;
    for(int i = 0; i < n; i++)
        if(dp[i][(1 << n) - 1] != INT_MAX && costs[i] != -1)
           ans = min(ans, dp[i][(1 << n) - 1] + costs[i]);

    if(ans == INT_MAX)
        return -1;
    return ans;
}
//----UNDIRECTED GRAPH---------------------------------------------------------------



class UndirectedGraph: public Graph{
public:
    UndirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, int cost=0, int capacity=0);
    ~UndirectedGraph() = default;

    vector<vector<int>> biconnectedComponents();
    vector<vector<int>> criticalEdges();
    bool havelHakimi(vector<int>degrees);

private:
    void biconnectedDFS(int node, int father, vector<int>& lowestLink,
                        vector<int>& nodeID, stack<int>& nodeStack,
                        vector<vector<int>>& bcc);

    void addBiconnected(stack<int>& nodeStack, int node, int neighbour,
                        vector<vector<int>>& bcc);

    void criticalEdgeDFS(int node, int father,vector<int>& lowestLink,
                         vector<int>& nodeID, vector<vector<int>>& critical);
};
//----------UndirectedGraph.cpp-------------------------------------------------------------------



UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}

void UndirectedGraph::addEdge(int node, int neighbour, int cost, int capacity)
{
    this -> setEdge(node, neighbour, cost, capacity);
    this -> setEdge(neighbour, node, cost, capacity);
}


vector<vector<int>> UndirectedGraph::biconnectedComponents()
{
    vector<vector<int>> bcc;
    stack<int> nodeStack;
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);

    for(int node = 1; node <= this -> getNrNodes(); node++)
    {
        if (nodeID.at(node) == -1)
            biconnectedDFS(node, 0, lowestLink,
                           nodeID, nodeStack, bcc);
    }
    return bcc;
}


void UndirectedGraph::biconnectedDFS(int node, int father,
                                     vector<int>& lowestLink,
                                     vector<int>& nodeID,
                                     stack<int>& nodeStack,
                                     vector<vector<int>>& bcc)
{
    nodeID[node] = nodeID[father]+1;
    lowestLink[node] = nodeID[father]+1;
    nodeStack.push(node);

    for (auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour;
        if (nodeID[neighbour] != -1 && neighbour != father)
            lowestLink[node] = min(lowestLink[node], nodeID[neighbour]);

        else if (neighbour != father)
        {
            biconnectedDFS(neighbour, node,
                           lowestLink, nodeID,
                           nodeStack, bcc);
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);

            if (lowestLink[neighbour] >= nodeID[node]) //node is an articulation point
                addBiconnected(nodeStack, node, neighbour, bcc);
        }

    }
}


void UndirectedGraph::addBiconnected(stack<int>& nodeStack, int node,
                                     int neighbour, vector<vector<int>>& bcc)
{
    /*
     * we stop popping at neighbour because between
     * neighbour and node (child and parent) there
     * might be other children of parent.
     * we then add neighbour and node to component
     * leaving node on stack as it might be part of
     * other components
     */
    vector<int>component;
    while (nodeStack.top() != neighbour)
    {
        component.push_back(nodeStack.top());
        nodeStack.pop();
    }
    nodeStack.pop();
    component.push_back(neighbour);
    component.push_back(node);
    bcc.push_back(component);
}


vector<vector<int>> UndirectedGraph::criticalEdges()
{
    vector<vector<int>> critical;
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    for(int node = 0; node < this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
        {
            criticalEdgeDFS(node, 0, lowestLink, nodeID,critical);
        }

    return critical;
}


void UndirectedGraph::criticalEdgeDFS(int node, int father,
                                      vector<int>& lowestLink,
                                      vector<int>& nodeID,
                                      vector<vector<int>>& critical)
{
    nodeID[node] = nodeID[father]+1;
    lowestLink[node] = nodeID[father]+1;

    for (auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour;
        if (nodeID[neighbour] == -1 && neighbour != father)
        {
            criticalEdgeDFS(neighbour, node, lowestLink,
                            nodeID,critical);
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);

            if (lowestLink[neighbour] > nodeID[node]) //node is an articulation point
                critical.push_back({node, neighbour});
        }
        else if (neighbour != father)
            lowestLink[node] = min(lowestLink[node], nodeID[neighbour]);
    }
}


bool UndirectedGraph::havelHakimi(vector<int> degrees)
{
    int loops = 0;
    while(true)
    {
        sort(degrees.begin(), degrees.end(), greater<>());

        if(degrees[0] == 0)
            return true;

        if(degrees[0] > degrees.size() - loops)
            return false;

        for(int i = 1; i <= degrees[0]; ++i)
            if(--degrees[i] < 0)
                return false;
        degrees[0] = 0;
        loops++;
    }
}

//---------DIRECTED GRAPH-----------------------------------------------------------------


class DirectedGraph: public Graph {
public:
    DirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, int cost=0, int capacity=0);
    ~DirectedGraph() = default;

    vector<vector<int>> getStronglyConnected();
    vector<int> topologicalSorting();
    int getMaxFlow(const int& start, const int& sink,
                   vector<vector<int>>& capacities);

private:
    void TarjanDFS(int start, int& counterID,
                          stack<int>& nodeStack, vector<bool>& onStack,
                          vector<vector<int>>& scc,
                          vector<int>& nodeID, vector<int>& lowestLink);

    void topologicalDFS(int node, vector<int>& sorted,
                        vector<bool>& visited);
    int EdmondsKarpBFS(const int& start, const int& sink, vector<int>& path,
                       vector<vector<int>>& capacities);

};

//---------DirectedGraph.cpp-----------------------------------------------------------



DirectedGraph::DirectedGraph(int _nrNodes): Graph(_nrNodes) {}


void DirectedGraph::addEdge(int node, int neighbour, int cost, int capacity)
{
   this -> setEdge(node, neighbour, cost, capacity);
}


vector<vector<int>> DirectedGraph::getStronglyConnected()
{ // initializing everything we need for the Tarjan algorithm
    vector<vector<int>> scc;
    stack<int> nodeStack;
    vector<bool> onStack(this -> getNrNodes()+1, false);
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    int counterID = 0;

    for(int node = 1; node <= this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
            TarjanDFS(node, counterID, nodeStack,
                      onStack, scc, nodeID, lowestLink);
    /*
     * scc = strongly connected component
     * TarjanDFS() modifies vector<vector<int>> scc
     * so vector<vector<int>> scc will contain all the needed components
     */

    return scc;
}


void DirectedGraph::TarjanDFS(int node, int& counterID,
                              stack<int>& nodeStack,
                              vector<bool>& onStack,
                              vector<vector<int>>& scc,
                              vector<int>& nodeID,
                              vector<int>& lowestLink)
{
    vector<int> component;
    nodeID[node] = counterID;
    lowestLink[node] = counterID++;
    nodeStack.push(node);
    onStack[node] = true;

    for(auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour; // node -> first; cost -> second
        if(nodeID[neighbour] == -1)         // if neighbour not visited
            TarjanDFS(neighbour, counterID, nodeStack,
                      onStack, scc, nodeID,
                      lowestLink);
        if(onStack[neighbour])          //if neighbour is on stack
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);
    }

    if(lowestLink[node] == nodeID[node])  // if this is true then node is the beginning of a scc
    {
        while(!nodeStack.empty())
        {
            int nodeToPop = nodeStack.top();
            component.push_back(nodeToPop);
            onStack[nodeToPop] = false;
            nodeStack.pop();
            if(nodeToPop == node)
                break;
        }

        scc.push_back(component);
        component.clear();
    }
}


vector<int> DirectedGraph::topologicalSorting()
{
    vector<int> sorted;
    vector<bool> visited(this->getNrNodes() + 1, false);
    for(int node = 1; node < visited.size(); ++node)
        if(!visited[node])
            topologicalDFS(node, sorted, visited);
    /*
     * -> TopologicalDFS() modifies the sorted vector
     * -> the sorted nodes are the nodes' times in descending order
     */
    return sorted;
}


void DirectedGraph::topologicalDFS(int node, vector<int>&sorted,
                                   vector<bool>&visited)
{
   visited[node] = true;
   for(auto &it: this->getNeighbours(node))
   {
       int neighbour = it.neighbour;
       if (!visited[neighbour])
           topologicalDFS(neighbour, sorted, visited);

   }
   sorted.push_back(node);
}


int DirectedGraph::getMaxFlow(const int& start, const int& sink,
                              vector<vector<int>>& capacities)
{
    int maxFlow = 0;
    vector<int>path;
    while(int bottleneck = EdmondsKarpBFS(start, sink, path, capacities))
    {
        maxFlow += bottleneck;
        int curr = sink;
        while(curr != start)
        {
            int prev = path[curr];
            capacities[prev][curr] -= bottleneck;
            capacities[curr][prev] += bottleneck; //back arch for augmented paths
            curr = prev;
        }

    }
    return maxFlow;
}


int DirectedGraph::EdmondsKarpBFS(const int &start, const int &sink,
                                  vector<int>& path, vector<vector<int>>& capacities)
{

    queue<pair<int, int>> toBeVisited;
    toBeVisited.push({start, INT_MAX}); //edge to start does not exist
    path.clear(); //starting fresh new path
    path.resize(getNrNodes()+1, -1);

    while(!toBeVisited.empty())
    {
        int node = toBeVisited.front().first;
        int capacity = toBeVisited.front().second;
        toBeVisited.pop();

        for(auto& next: getNeighbours(node))
        {
            int cpc = capacities[node][next.neighbour];
            if(cpc && path[next.neighbour] == -1)
            {
                path[next.neighbour] = node;
                int bottleneck = min(capacity, cpc);
                if(next.neighbour == sink)
                    return bottleneck;
                toBeVisited.push({next.neighbour, bottleneck});

            }
        }
    }

    return 0;
}

//---------Problem Solvers----------------------------------------------------------------



void DFS_INFO_ARENA()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int n, m, x, y;
    fin >> n >> m;
    UndirectedGraph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        ug.addEdge(x, y);
    }
    fout << ug.nrConnectedComponents();
}



void BFS_INFO_ARENA()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    int n, m, x, y, s;
    fin >> n >> m >> s;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y);
    }
    vector<int> ans = dg.getDistancesBFS(s);
    for(int i = 1 ; i <= dg.getNrNodes(); i++)
        fout << ans[i] << " ";
}



void SCC_INFO_ARENA()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n, m, x, y;
    fin >> n >> m;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y);
    }
    vector<vector<int>> scc = dg.getStronglyConnected();
    fout << scc.size()<< "\n";

    for(auto &comp: scc)
    {
        for(auto &elem: comp)
            fout << elem << " ";
        fout << "\n";
    }
}



void TOPOLOGICAL_SORT_INFO_ARENA()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    int n, m, x, y;
    fin >> n >> m;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y);
    }
    vector<int> ans = dg.topologicalSorting();
    for(int i = ans.size()-1; i >= 0; i--)
        fout << ans.at(i)<< " ";

}



void BCC_INFO_ARENA()
{
    const rlim_t new_stackSize = 20000000;
    struct rlimit limit;
    getrlimit(RLIMIT_STACK, &limit);
    limit.rlim_cur = new_stackSize;
    setrlimit(RLIMIT_STACK, &limit);

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m, x, y;
    fin >> n >> m;
    UndirectedGraph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        ug.addEdge(x, y);
    }
    vector<vector<int>> ans = ug.biconnectedComponents();

    fout << ans.size()<< " ";
    for(auto &comp: ans)
    {
        for(auto &elem: comp)
            fout << elem << " ";
        fout << "\n";
    }
}



vector<vector<int>> CRITICAL_CONN_LEETCODE(int n, vector<vector<int>>& connections)
{
    UndirectedGraph ug(n);
    int m = connections.size();
    for(int i = 0; i < m ; ++i)
        ug.addEdge(connections[i][0], connections[i][1]);

    return ug.criticalEdges();

}



void HAVEL_HAKIMI()
{
    int n, d;
    cout << "Insert the number of nodes: ";
    cin >> n;
    cout << "\n";
    cout << "Insert the degree of each node: ";
    UndirectedGraph ug(n);
    vector<int>degrees;
    for(int i = 0; i < ug.getNrNodes(); i++)
    {
        cin >> d;
        degrees.push_back(d);
    }
    cout << "\n";
    cout << ug.havelHakimi(degrees);
}



void MIN_SPANNING_TREE_INFO_ARENA()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, x, y, c;
    fin >> n >> m;
    UndirectedGraph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        ug.addEdge(x, y, c);
    }
    int costMST = 0;
    vector<int> ans = ug.Graph::PrimMST(costMST);

    fout << costMST << "\n";
    fout << n - 1 << "\n";
    for(int i = 2; i < ans.size(); i++)
        fout<< ans[i] << " "<< i << "\n";
}



void DIJKSTRA_INFO_ARENA()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, x, y, c;
    fin >> n >> m;
    Graph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        dg.setEdge(x, y, c);
    }

    vector<int> ans = dg.Dijkstra(1);
    for(unsigned i = 2; i < ans.size(); i++)
        if(ans[i] != INT_MAX)
          fout << ans[i]<< " ";
        else
          fout << 0 << " ";
}



void BELLMAN_FORD_INFO_ARENA()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int n, m, x, y, c;
    fin >> n >> m;
    Graph g(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        g.setEdge(x, y, c);
    }

    vector<int> ans = g.BellmanFord(1);
    if(ans[0] == -1)
        fout << "Ciclu negativ!";
    else
    for(unsigned i = 2; i < ans.size(); i++)
        fout << ans[i]<< " ";
}



 void DISJOINT_SETS_INFO_ARENA()
{
    ifstream fin("disjoint.in");
    ofstream fout("disjoint.out");
    int n, m, x, y, op;
    fin >> n >> m;
    vector<bool> sameGroup;
    vector<int> root(n+1);

    for(int i = 1; i <= n; i++)
        root[i] = i;

    for(int i = 1; i <= m; i++)
    {
        fin >> op >>x >> y;
        Graph::disjointSets(op, x, y, sameGroup, root);
    }
    for(int i = 0; i < sameGroup.size(); i++)
        if(sameGroup[i])
            fout << "DA" << "\n";
        else
            fout << "NU" << "\n";
}



void ROY_FLOYD_INFO_ARENA()
{
    ifstream fin("royfloyd.in");
    ofstream fout("royfloyd.out");
    int n, cost;
    fin >> n;
    Graph g(n);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            fin >> cost;
            g.setEdge(i, j, cost);
            //setEdge will push_back j starting from index 0!
        }
    vector<vector<int>> ans = g.getMinCostMatrix();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            fout << ans[i][j] << " ";
        fout << "\n";
    }

}



void TREE_DIAMETER_INFO_ARENA()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    int n, x, y;
    fin >> n;
    UndirectedGraph ug(n);
    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        ug.addEdge(x, y);
    }
    fout <<  ug.Graph::getTreeDiameter(1);

}



void MAX_FLOW_INFO_ARENA()  //60p
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    int n, m, x, y, capacity;
    fin >> n >> m;
    DirectedGraph dg(n);

    for(int i = 0; i < m; i++)
    {
        fin >> x >> y >> capacity;
        dg.addEdge(x, y, 0, capacity);
    }
    vector<vector<int>> cap;
    cap.resize(n+1);

    for(int i = 1; i <= n; i++)
    {
        cap[i].resize(n+1, 0);
        for(auto& it: dg.getNeighbours(i))
            cap[i][it.neighbour] = it.capacity;
    }

    fout << dg.getMaxFlow(1, n, cap);

}



void TRAVELLING_SALESMAN_INFO_ARENA()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int n, m, x, y, cost;
    fin >> n >> m;
    DirectedGraph dg(n);
    vector<vector<int>> costs(n);
    for(int i = 0; i < n; i++)
        costs[i].resize(n, -1);

    for(int i = 0; i < m; i++)
    {
        fin >> x >> y >> cost;
        dg.addEdge(x, y, cost);
        costs[y][x] = cost;
    }

   int ans = dg.Graph::getMinSalesmanCost(0, costs[0]); // start, costs[start]
   if(ans != -1)
       fout << ans;
   else
       fout << "Nu exista solutie";
}

//---------------------------------------------

int main()
{
    // Run a problem solver or make one yourself

    DFS_INFO_ARENA();
    return 0;
}