#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;


struct Weighted_Edge{

    int u,v,weight;

    Weighted_Edge(int a, int b, int c):u(a),v(b),weight(c){}
    ~Weighted_Edge() = default;

    bool operator<(const Weighted_Edge &b) const
    {
        return this->weight<b.weight;
    }
};

class Graph{
private:
    int n;
    vector<vector<int>> la;
    vector<pair<int,int>> edges;
    vector<Weighted_Edge> weighted_edges;
    vector<vector<pair<int,int>>> weighted_adjacency_list;
    vector<vector<int>> dist_matrix;

    void dfs(int nod_crt, vector<bool> &viz);

    void dfs_biconexe(int nod_crt, vector<int>& lowest, vector<int>& level, vector<int>& father, vector<vector<int>>& biconnected_components, stack<pair<int,int>>& edges);
    void add_biconnected_component(int x, int y, vector<vector<int>>& biconnected_components, stack<pair<int,int>>& edges);
    void dfs_tarjan(int nod_crt, int& index, stack<int>& S, vector<bool>& onstack, vector<int>& level, vector<int>& lowest, vector<vector<int>>& strongly_connected_components);
    bool max_flow_bfs(int source, int terminal, vector<vector<int>>& flow, vector<vector<int>>& capacity, vector<int>& pred, vector<bool>& viz);
    bool bfs_HK(vector<int>& pairU, vector<int>& pairV, vector<int>& dist);
    bool dfs_HK(vector<int>& pairU, vector<int>& pairV, vector<int>& dist, const int u);

    void static update_disjoint(int x, vector<int> &father);
    bool static consume(int nr, int poz, vector<int>& degrees);

public:
    Graph(int nr_noduri, vector<vector<int>>& adj_list):n(nr_noduri), la(adj_list){}
    Graph(int nr_noduri, vector<pair<int,int>>& edges_list):n(nr_noduri), edges(edges_list){}
    Graph(int nr_noduri, vector<Weighted_Edge>& w_edges_list):n(nr_noduri), weighted_edges(w_edges_list){}
    Graph(int nr_noduri, vector<vector<pair<int,int>>>& w_adj_list):n(nr_noduri), weighted_adjacency_list(w_adj_list){}
    Graph(int nr_noduri, vector<vector<int>>& distMatrix, bool dummy):n(nr_noduri), dist_matrix(distMatrix){}
                                                        /// i actually had to use a dummy bool because there was an overload on constructor...
    ~Graph() = default;

    void add_edge(int from, int to){
        la[from].push_back(to);
    }

    vector<int> bfs_distances(int start=1); /// Starting from node 1 by default
    int no_connected_components(); /// uses dfs
    vector<int> topological_sort();

    vector<vector<int>> get_biconnected_components();
    vector<vector<int>> get_strongly_connected_components();

    vector<int> get_distances_Dijkstra(const int start_node, const int inf);
    vector<int> get_distances_BellmanFord(const int start);
    vector<int> get_distances_SPFA(const int start);

    int APM_Kruskal(vector<pair<int,int>>& chosen_edges);
    int TD();

    void royFloydWarshall(vector<vector<int>>& pred);

    int max_flow(int source, int terminal);

    int min_hamiltonian_cycle(int inf);
    vector<int> find_eulerian_cycle(); /// if the returned vector is empty then there is no eulerian cycle

    vector<pair<int,int>> bipartite_max_matching(const int n1, const int n2);

    bool static Havel_Hakimi(vector<int> &grade_noduri);
    void static solve_disjoint(istream &in, ostream &out);
};


vector<int> Graph::bfs_distances(int start)
{
    vector<int> dist(n+1, -1);
    queue<int> q;
    int nod_crt;

    q.push(start);
    dist[start]=0;

    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin: la[nod_crt])
        {
            if(dist[nod_vecin] == -1)
            {
                dist[nod_vecin] = dist[nod_crt] + 1;
                q.push(nod_vecin);
            }
        }
    }

    return dist;
}

int Graph::no_connected_components()
{
    vector<bool> viz(n+1, false);
    int nr_c=0;
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            ++nr_c;
            dfs(i, viz);
        }
    }

    return nr_c;
}


vector<int> Graph::topological_sort()
{
    vector<int> zero_nodes; /// contains nodes/vertices with internal degree 0
    vector<int> degrees(n+1,0);
    int i;
    for(i=1; i<=n; ++i)
    {
        for(auto nod_vecin: la[i])
            ++degrees[nod_vecin];
    }
    for(i=1; i<=n;++i)
        if(degrees[i] == 0)
            zero_nodes.push_back(i);
    if(zero_nodes.empty())
        return zero_nodes;

    for(unsigned int i=0; i<zero_nodes.size(); ++i)
    {
        for(auto nod_vecin: la[zero_nodes[i]])
        {
            --degrees[nod_vecin];
            if(degrees[nod_vecin] == 0)
                zero_nodes.push_back(nod_vecin);
        }
    }
    if(zero_nodes.size() < n) /// if there are less than n nodes in the vector then there is at least 1 cycle in the graph so it can't be sorted
        zero_nodes.clear();   /// return empty vector to signal that the graph isn't a DAG

    return zero_nodes;
}

void Graph::dfs(int nod_crt, vector<bool> &viz)
{
    for(auto nod_vecin: la[nod_crt])
    {
        if(!viz[nod_vecin])
        {
            viz[nod_vecin] = true;
            dfs(nod_vecin, viz);
        }
    }
}


void Graph::add_biconnected_component(int x, int y, vector<vector<int>>& biconnected_components, stack<pair<int,int>>& edges)
{
    int a,b;
    vector<int> component;
    do
    {
        a=edges.top().first;
        b=edges.top().second;

        edges.pop();

        component.push_back(a);
        component.push_back(b);

    }while((a!=x || b!=y) && !edges.empty());

    sort(component.begin(), component.end() );
    /// each component contains duplicate values at this point;
    /// values are sorted so the equal values are adjacent
    /// remove them with std:unique before pushing to solution;

    auto it = unique(component.begin(), component.end()); /// return iterator after the last non-removed element
    component.resize(distance(component.begin(), it));  /// resize the vector because there are undefined elements at the end for each removed element

    biconnected_components.push_back(component);
}

void Graph::dfs_biconexe(int nod_crt, vector<int>& lowest, vector<int>& level, vector<int>& father, vector<vector<int>>& biconnected_components, stack<pair<int,int>>& edges)
{
    level[nod_crt] = level[father[nod_crt]] + 1;
    lowest[nod_crt] = level[nod_crt];

    for(auto nod_vecin: la[nod_crt])
    {
        if(level[nod_vecin] == 0) /// node hasn't been visited so far
        {
            father[nod_vecin] = nod_crt;
            edges.push(make_pair(nod_crt, nod_vecin));

            dfs_biconexe(nod_vecin, lowest, level, father, biconnected_components, edges);

            if(lowest[nod_vecin] >= level[nod_crt]) /// found an articulation point -> close a biconnected component
                add_biconnected_component(nod_crt, nod_vecin, biconnected_components, edges);

            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(nod_vecin!= father[nod_crt]) /// back edge
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);;
    }


}

vector<vector<int>> Graph::get_biconnected_components()
{
    vector<int> lowest(n+1, 0), level(n+1, 0), father(n+1, 0);
    vector<vector<int>> biconnected_components;
    stack<pair<int,int>> edges;

    dfs_biconexe(1, lowest, level, father, biconnected_components, edges);

    return biconnected_components;
}



void Graph::dfs_tarjan(int nod_crt, int& index, stack<int>& S, vector<bool>& onstack, vector<int>& level, vector<int>& lowest, vector<vector<int>>& strongly_connected_components)
{
    ++index;
    level[nod_crt] = index;
    lowest[nod_crt] = index;
    S.push(nod_crt);
    onstack[nod_crt] = true;

    for(auto nod_vecin : la[nod_crt])
    {
        if(level[nod_vecin]==0)
        {
            dfs_tarjan(nod_vecin, index, S, onstack, level, lowest, strongly_connected_components);
            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(onstack[nod_vecin])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);
    }

    if(level[nod_crt] == lowest[nod_crt])
    {
        vector<int> scc;
        int st;
        do
        {
            st = S.top();
            S.pop();
            onstack[st]=false;
            scc.push_back(st);
        }while(st!=nod_crt);

        strongly_connected_components.push_back(scc);
    }

}

vector<vector<int>> Graph::get_strongly_connected_components()
{
    stack<int> S;
    vector<bool> onstack(n+1, false);
    vector<int> lowest(n+1, 0), level(n+1, 0);
    vector<vector<int>> strongly_connected_components;
    int index=0;

    for(int i=1;i<=n;++i)
        if(level[i] == 0)
            dfs_tarjan(i, index, S, onstack, level, lowest, strongly_connected_components);

    return strongly_connected_components;
}


vector<int> Graph::get_distances_BellmanFord(const int start)
{
    vector<int> distance(n+1, 1<<29);
    distance[start] = 0;
    bool ok=true;
    for(int i=1; i<n && ok==true;++i)
    {
        ok = false;
        for(auto x: weighted_edges)
            if(distance[x.u] + x.weight < distance[x.v])
            {
                distance[x.v] = distance[x.u] + x.weight ;
                ok = true;
            }
    }
    for(auto x: weighted_edges)
        if(distance[x.u] + x.weight < distance[x.v]) /// there is a negative cycle -> return empty vector to signal
        {
            distance.clear();
            return distance;
        }
    return distance;
}

vector<int> Graph::get_distances_SPFA(const int start)
{
    vector<int> nr_updates(n+1, 0);
    queue<int> candidate_vertices;
    vector<bool> is_candidate(n+1, false);
    vector<int> distance(n+1, 1<<29);

    distance[start] = 0;
    candidate_vertices.push(start);
    is_candidate[start] = true;

    int vertex;

    while(candidate_vertices.empty() == false)
    {
        vertex = candidate_vertices.front();
        candidate_vertices.pop();
        is_candidate[vertex] = false;

        ++nr_updates[vertex];
        if(nr_updates[vertex] == n) /// more than n updates from the same vertex -> negative cycle -> return empty vector;
        {
            distance.clear();
            return distance;
        }

        for(auto &w_edge: weighted_adjacency_list[vertex]) /// w_edge is a pair (c,v), meaning there is a directed arc from vertex to v with weight c
        {
            if(w_edge.first + distance[vertex] < distance[w_edge.second])
            {
                distance[w_edge.second] = w_edge.first + distance[vertex];
                if(!is_candidate[w_edge.second])
                {
                    candidate_vertices.push(w_edge.second);
                    is_candidate[w_edge.second] = true;
                }
            }
        }
    }
    return distance;
}


void Graph::update_disjoint(int x, vector<int> &father)
{
    if(x!=father[x])
        update_disjoint(father[x], father);
    father[x] = father[father[x]];
}

int  Graph::APM_Kruskal(vector<pair<int,int>>& chosen_edges) /// Returns the total cost of the APM
{                                                            /// and a vector of pairs representing the chosen edges
    int nr_chosen = 0, sum=0;
    unsigned int i=0;
    int x, y;
    vector<int> father(n+1);
    vector<int> height(n+1,0);

    chosen_edges.clear();
    for(int k=1; k<=n; ++k)
        father[k] = k;
    sort(weighted_edges.begin(), weighted_edges.end());

    while(i<weighted_edges.size() && nr_chosen<n-1)
    {
        x = weighted_edges[i].u;
        y = weighted_edges[i].v;

        while(father[x]!=x)
            x=father[x];
        while(father[y]!=y)
            y=father[y];

        if(x != y) /// the nodes are not in the same tree so far so we choose it as a part of the APM
        {
            sum += weighted_edges[i].weight;
            ++nr_chosen;
            chosen_edges.push_back(make_pair(weighted_edges[i].u, weighted_edges[i].v)); /// add edge to the list of selected edges

            if(height[x] > height[y])
                father[y] = x;       /// y becomes a part of x's tree and height of x stays the same
            else if(height[x] < height[y])
                father[x] = y;       /// x becomes a part of y's tree and height of y stays the same
            else
            {
                father[y] = x;       /// the tree of root x and the tree of root y have the same height
                ++height[x];         /// either one can become the main root but the height is increased by 1
            }
        }
        ++i;
    }
    return sum;
}

void Graph::solve_disjoint(istream &in, ostream &out)
{
    int n,m;
    int op, x, y;
    in>>n>>m;

    vector<int> father(n+1);

    for(int k=1; k<=n; ++k)
        father[k] = k;

    for(int i=0;i<m;++i)
    {
        in>>op>>x>>y;
        update_disjoint(x, father);
        update_disjoint(y, father);
        if(op == 1)
            father[father[y]] = father[x];
        else
        {
            if(father[x] == father[y])
                out<<"DA\n";
            else
                out<<"NU\n";
        }
    }
}


vector<int> Graph::get_distances_Dijkstra(const int start_node, const int inf)
{   /// unreachable vertices will have distance inf in the distance vector;
    /// when calling this function make sure to use and appropriate value for inf
    /// based on the values you are working with;
    int nod_crt, d;
    vector<int> distance(n+1, inf);
    distance[start_node] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > min_dist_node;
    min_dist_node.push(make_pair(distance[start_node], start_node));

    while(min_dist_node.empty() == false)
    {
        d = min_dist_node.top().first;        /// the top is the closest vertex to the start_node that should be considered for a possible update
        nod_crt = min_dist_node.top().second;
        min_dist_node.pop();

        if(d == distance[nod_crt])
        {
            for(auto edge:weighted_adjacency_list[nod_crt]) /// edge is a pair<int, int> representing (cost, adjacent_vertex)
            {
                if(d + edge.first < distance[edge.second])
                {
                    distance[edge.second] =  d + edge.first;
                    min_dist_node.push(make_pair(distance[edge.second], edge.second));
                }
            }
        }
    }
    return distance;
}

int Graph::TD()
{
    queue<int> q;
    vector<bool> viz(n+1,false);
    vector<int> dist(n+1, 1);

    q.push(1);
    viz[1]=true;
    int nod_crt;
    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin:la[nod_crt])
        {
            if(!viz[nod_vecin])
            {
                viz[nod_vecin]=true;
                q.push(nod_vecin);
            }
        }
    }
    for(auto i=1;i<viz.size();++i)
        viz[i]=false;

    q.push(nod_crt);
    viz[nod_crt] = true;
    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin:la[nod_crt])
        {
            if(!viz[nod_vecin])
            {
                viz[nod_vecin]=true;
                q.push(nod_vecin);
                dist[nod_vecin] = dist[nod_crt]+1;
            }
        }
    }
    return dist[nod_crt];
}

void Graph::royFloydWarshall(vector<vector<int>>& pred)
{
    for(int k=0; k<n; ++k)
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                if(dist_matrix[i][j] > dist_matrix[i][k] + dist_matrix[k][j])
                {
                    dist_matrix[i][j] = dist_matrix[i][k] + dist_matrix[k][j];
                    pred[i][j] = pred[k][j];
                }
}


int Graph::max_flow(int source, int terminal)
{
    vector<vector<int>> flow(n+1, vector<int>(n+1,0));   /// acts as a mix of the residual graph and the graph of flow -> positive values = flow;
    vector<vector<int>> capacity(n+1, vector<int>(n+1,0));                                                       /// negative values = reverse flow;
    la.clear();
    la.resize(n+1);

    vector<int> pred(n+1, 0);
    vector<bool> visited(n+1, false);

    int maximum_flow=0;

    for(auto& edge:weighted_edges)
    {
        capacity[edge.u][edge.v] = edge.weight;
        if(!capacity[edge.v][edge.u]) /// If i didn't previously encounter a v->u edge
        {                             /// add u and v to each others list for easier bf
            la[edge.u].push_back(edge.v);
            la[edge.v].push_back(edge.u);
        }
    }

    max_flow_bfs(source, terminal, flow, capacity, pred, visited);
    while(visited[terminal])
    {
        for(auto& nod_vecin:la[terminal])
        {
            if(flow[nod_vecin][terminal] < capacity[nod_vecin][terminal] && visited[nod_vecin]) /// vertex has been reached and we can make improvements
            {
                int min_flow = capacity[nod_vecin][terminal] - flow[nod_vecin][terminal];
                int nod_crt = nod_vecin;

                while(nod_crt != source) /// find the residual capacity
                {
                    min_flow = min(min_flow, capacity[pred[nod_crt]][nod_crt] - flow[pred[nod_crt]][nod_crt]);
                    nod_crt = pred[nod_crt];                          /// if flow is negative -> reverse edge -> capacity = 0
                }                                                     /// so u end up with abs(flow) in that case;

                flow[nod_vecin][terminal] += min_flow;
                flow[terminal][nod_vecin] -= min_flow;

                maximum_flow += min_flow;

                nod_crt = nod_vecin;
                while(nod_crt != source) /// update flow
                {
                    flow[pred[nod_crt]][nod_crt] += min_flow;
                    flow[nod_crt][pred[nod_crt]] -= min_flow;
                    nod_crt = pred[nod_crt];
                }
            }
        }
        fill(visited.begin(), visited.end(), false);
        max_flow_bfs(source, terminal, flow, capacity, pred, visited);
    }
    /// should somehow return last instance of visited for the min-cut;
    /// maybe use maximum_flow as referenced parameter and return viz;
    return maximum_flow;
}

bool Graph::max_flow_bfs(int source, int terminal, vector<vector<int>>& flow, vector<vector<int>>& capacity, vector<int>& pred, vector<bool>& viz)
{
    queue<int> bf_vertices;
    bf_vertices.push(source);

    int nod_crt;

    while(!bf_vertices.empty())
    {
        nod_crt = bf_vertices.front();
        bf_vertices.pop();

        for(auto nod_vecin: la[nod_crt])
        {
            if(flow[nod_crt][nod_vecin] < capacity[nod_crt][nod_vecin] && !viz[nod_vecin])
            {
                viz[nod_vecin] = true;

                if(nod_vecin != terminal)
                {
                    pred[nod_vecin] = nod_crt;
                    bf_vertices.push(nod_vecin);
                }
            }
        }
    }
    return viz[terminal];
}

int Graph::min_hamiltonian_cycle(int inf = 0x1fffffff )
{
    int n2 = 1<<n; /// this is why should be <32
    vector<vector<int>> cost(n,vector<int>(n,inf));
    vector<vector<int>> path_cost(n2, vector<int>(n,inf));  /// path_cost[i][j] = the min cost of a path that ends in vertex j
                                                            /// and contains all vertexes k such that (1<<k) & i = (1<<k);
                                                            /// ~~ k is hashed inside i
                                                            /// min hamiltonian cycle cost becomes min(path_cost[(1<<n)-1][j] + cost[j][i])
                                                            /// for any i chosen arbitrarily and all vertices j such that j->i;
    la.clear();
    la.resize(n);

    for(auto& edge: weighted_edges)
    {
        la[edge.v].push_back(edge.u); /// reverse adjacency list to make it easier to find all js described above |^|
        cost[edge.u][edge.v] = edge.weight;
    }

    path_cost[1][0] = 0; /// = path that ends in vertex 0 and only has vertex 0 in it

    for(int i=2; i<n2; ++i)
    {
        for(int j=0; j<n; ++j) /// walk through all vertices to find those in the current path i
        {
            if(i & (1<<j)) /// if j is in path hashed by i compute min path_cost of a path i that end on j
            {
                for(auto k: la[j]) /// there is an edge k->j;
                {
                    if(i & (1<<k)) /// k is also in path i and there is an edge k->j
                        path_cost[i][j] = min(path_cost[i][j], path_cost[i ^ (1<<j)][k] + cost[k][j]);
                        /// min of (current path i to j) and (the path that leads to k and doesn't contain j + cost from k to j)
                        /// since i & (1<<j) is true, i ^ (1<<j) is the same as i - (1<<j) which is smaller than i so it has already been computed
                }
            }
        }
    }
    int min_cost = inf;

    for(auto k:la[0])/// close the cycle;
        min_cost = min( min_cost, path_cost[n2-1][k] + cost[k][0]);

    return min_cost; /// if there was no hamiltonian cycle min_cost will remain inf so the return value has to be evaluated;
                     /// can't return -1/0 since the graph might as well have negative values;
}

vector<int> Graph::find_eulerian_cycle()
{
    vector<int> cycle;
    vector<vector<int>> my_edges(n+1); /// my_edges[i] = the edges that have i as an endpoint - stored as indexes of edges
    vector<bool> available_edges(edges.size(), true); /// available_edges[i]=true if the edge with index i has not been used so far in the cycle
    vector<int> vertices_stack; /// used to avoid stack overflow in recursive dfs;

    for(auto i=0; i<edges.size(); ++i)
    {
        my_edges[edges[i].first].push_back(i);
        my_edges[edges[i].second].push_back(i);
    }

    for(auto i=1; i<=n; ++i)
        if(my_edges[i].size() & 1) /// vertex i has an odd number of edges -> there is no eulerian cycle
            return cycle;

    vertices_stack.push_back(1);

    while(!vertices_stack.empty())
    {
        auto crt_node = vertices_stack.back(); /// take the last vertex === top of the stack

        if(my_edges[crt_node].size()) /// if the current vertex still has edges
        {
            auto edge_index = my_edges[crt_node].back(); /// take the last edge since it's easier to remove with pop_back() after it's used
            my_edges[crt_node].pop_back();

            if(available_edges[edge_index]) /// if the edge hasn't been used already (by the vertex at the other end of it)
            {
                available_edges[edge_index] = false;
                auto next_node = crt_node ^ edges[edge_index].first ^ edges[edge_index].second;
                        /// either edges[edge_index].second or edges[edge_index].first has to be = to crt_node
                        /// and by using xor they cancel out;
                        /// alternative: next_node = (crt_node == edges[edge_index].second)? edges[edge_index].first : edges[edge_index].second
                vertices_stack.push_back(next_node);
            }
        }
        else
        {
            vertices_stack.pop_back();
            cycle.push_back(crt_node);
        }
    }


    return cycle; /// cycle[i] - cycle[i+1] represents an edge
                 /// last vertex is the same as the first vertex
}


bool Graph::bfs_HK(vector<int>& pairU, vector<int>& pairV, vector<int>& dist)
{
    queue<int> nodes;
    const int inf = 0x1fffffff;
    for(auto i=1; i<pairU.size(); ++i)
    {
        if(pairU[i] == 0)
        {
            dist[i] = 0;
            nodes.push(i);
        }
        else
            dist[i] = inf;
    }
    dist[0] = inf;

    while(nodes.empty() == false)
    {
        int u = nodes.front();
        nodes.pop();

        if(dist[u] < dist[0])
        {
            for(auto v:la[u])
            {
                if(dist[pairV[v]] == inf)
                {
                    dist[pairV[v]] = dist[u]+1;
                    nodes.push(pairV[v]);
                }
            }
        }
    }

    return dist[0] != inf;
}

bool Graph::dfs_HK(vector<int>& pairU, vector<int>& pairV, vector<int>& dist, const int u)
{
    if(u)
    {
        for(auto v:la[u])
        {
            if(dist[pairV[v]] == dist[u]+1)
            {
                if(dfs_HK(pairU, pairV, dist, pairV[v]))
                {
                    pairU[u] = v;
                    pairV[v] = u;
                    return true;
                }
            }
        }
        dist[u] = 0x1fffffff; /// inf
        return false;
    }
    return true;
}


vector<pair<int,int>> Graph::bipartite_max_matching(const int u, const int v)
{
    vector<int> pairU(u+1,0), pairV(v+1, 0);
    vector<int> dist(u+1);

    while(bfs_HK(pairU, pairV, dist))
    {
        for(auto i=1; i<=u; ++i)
            if(pairU[i] == 0)
                dfs_HK(pairU, pairV, dist, i);
    }

    vector<pair<int,int>> matchings;
    for(auto i=1; i<=u; ++i)
            if(pairU[i])
                matchings.push_back({i, pairU[i]});

    return matchings;
}

/// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool Graph::consume(int nr, int poz, vector<int>& degrees)
{
    if(nr == 0)
        return true;
    if(poz == 0)
        return false;

    if(nr>degrees[poz])
    {
        bool ok = consume(nr-degrees[poz], poz-1, degrees);

        degrees[poz-1]+=degrees[poz];
        degrees[poz]=0;
        return ok;
    }

    degrees[poz-1]+=nr;
    degrees[poz]  -=nr;

    return true;
}

bool Graph::Havel_Hakimi(vector<int>& grade_noduri)
{
    int n=grade_noduri.size(), sum=0, max_grade = 0;
    vector<int> degrees(n, 0);
    for(auto x: grade_noduri)
    {
        if(x>=n)
            return false;

        ++degrees[x];
        sum+=x;

        if(x>max_grade)
            max_grade = x;
    }
    if( sum & 1)
        return false;

    for(int i=max_grade; i; --i)
    {
        while(degrees[i])
        {
            --degrees[i];
            if(!consume(i, i, degrees))
                return false;
        }
    }
    return true;
}




/// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


void solve_cmp_biconexe()
{
    /*
    ifstream f("biconexe.in");
    ofstream g("biconexe.out");
    int n,m;
    f>>n;
    f>>m;
    int a,b;
    for(; m; --m)
    {
        f>>a>>b;
        ///gr.add_edge(a,b);
        ///gr.add_edge(b,a);
    }

    vector<vector<int>> biconnected_components = gr.get_biconnected_components();

    g<<biconnected_components.size()<<'\n';
    for(auto component:biconnected_components)
    {
        g<<component[0];
        for(auto i=1;i<component.size();++i)
            if(component[i]!=component[i-1])
                g<<' '<<component[i-1];
        g<<'\n';
    }
    */
}


void ia_solve_bfs()
{
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    int n,m,s;
    int a,b;
    f>>n>>m>>s;

    vector<vector<int>> adjList(n+1, vector<int>(0));

    for(; m; --m)
    {
        f>>a>>b;
        adjList[a].push_back(b);
    }
    f.close();
    Graph gr(n, adjList);

    auto distances = gr.bfs_distances(s);

    for(int i=1; i<=n; ++i)
        g<<distances[i]<<' ';
    g.close();
}

void ia_solve_dfs()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int n,m;
    int a,b;
    f>>n>>m;

    vector<vector<int>> adjList(n+1, vector<int>(0));

    for(; m; --m)
    {
        f>>a>>b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    f.close();
    Graph gr(n, adjList);
    g<<gr.no_connected_components();
    g.close();
}

void ia_solve_biconex()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    int n,m;
    int a,b;
    f>>n>>m;

    vector<vector<int>> adjList(n+1, vector<int>(0));

    for(; m; --m)
    {
        f>>a>>b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    f.close();
    Graph gr(n, adjList);
    auto comp_biconexe = gr.get_biconnected_components();
    g<<comp_biconexe.size();
    for(auto& comp: comp_biconexe)
    {
        g<<'\n';
        for(auto nod:comp)
            g<<nod<<' ';
    }
    g.close();
}

void ia_solve_ctc()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m;
    int a,b;
    f>>n>>m;

    vector<vector<int>> adjList(n+1, vector<int>(0));

    for(; m; --m)
    {
        f>>a>>b;
        adjList[a].push_back(b);
    }
    f.close();
    Graph gr(n, adjList);
    auto ctcs = gr.get_strongly_connected_components();
    g<<ctcs.size();
    for(auto& ctc: ctcs)
    {
        g<<'\n';
        for(auto nod:ctc)
            g<<nod<<' ';
    }
    g.close();
}

void ia_solve_sortaret()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int n,m;
    int a,b;
    f>>n>>m;

    vector<vector<int>> adjList(n+1, vector<int>(0));

    for(; m; --m)
    {
        f>>a>>b;
        adjList[a].push_back(b);
    }
    f.close();
    Graph gr(n, adjList);
    auto sorted = gr.topological_sort();
    for(auto nod: sorted)
        g<<nod<<' ';
    g.close();
}


void ia_solve_apm()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m;
    int a,b,c;
    f>>n>>m;
    vector<Weighted_Edge> w_edges_list;

    for(; m; --m)
    {
        f>>a>>b>>c;
        w_edges_list.push_back({a,b,c});
    }
    f.close();
    Graph gr(n, w_edges_list);

    vector<pair<int,int>> chosen_edges;
    int cost = gr.APM_Kruskal(chosen_edges);

    g<<cost<<'\n'<<n-1<<'\n';
    for(auto edge: chosen_edges)
        g<<edge.first<<' '<<edge.second<<'\n';
    g.close();
}

int main()
{
    /// ia_solve_bfs();
    /// ia_solve_dfs();
    /// ia_solve_biconex();
    /// ia_solve_ctc();
    /// ia_solve_sortaret();
    ia_solve_apm();
    return 0;
}

    /* bipartite max matching
    int u,v,m;
    int a,b;

    f>>u>>v>>m;
    vector<pair<int,int>> edges;
    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        edges.push_back({a,b});
    }
    auto matchings = Graph::bipartite_max_matching(u,v,edges);

    g<<matchings.size()<<'\n';
    for(auto match: matchings)
        g<<match.first<<' '<<match.second<<'\n';

    f.close();
    g.close();
    return 0;
    */

/* eulerian cycle
    int n,m;
    int a,b;

    f>>n>>m;
    vector<pair<int,int>> edges;
    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        edges.push_back({a,b});
    }
    auto cycle = Graph::find_eulerian_cycle(n, edges);

    if(cycle.size())
    {
        for(auto i=0;i<cycle.size()-1 ; ++i)
            g<<cycle[i]<<' ';
    }
    else
    {
        g<<-1;
    }


    f.close();
    g.close();
    return 0;
*/


/*
int n,m;
    int a,b,c;
    const int inf = 0xfff;

    f>>n>>m;
    vector<Weigthed_Edge> DWG;

    for(int i=0;i<m;++i)
    {
        f>>a>>b>>c;
        DWG.push_back(Weigthed_Edge(a,b,c));
    }
    auto min_cost = Graph::min_hamiltonian_cycle(n, DWG);

    if(min_cost == 0x1fffffff)
        g<<"Nu exista solutie";
    else
        g<<min_cost;

*/

/* max flow

int a,b,c;
    vector<Weigthed_Edge> DWG;

    f>>n>>m;
    for(int i=0;i<m;++i)
    {
        f>>a>>b>>c;
        DWG.push_back(Weigthed_Edge(a,b,c));
    }
    g<<Graph::max_flow(n,1,n,DWG);

*/


/* royFloydWarshall to add to linker function for infoarena when I remake the class;
    const int inf = 100000;
    f>>n;
    vector<vector<int>> adjMat(n, vector<int>(n, inf));
    vector<vector<int>> pred(n, vector<int>(n,-1));
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
        {
            f>>c;
            if(c)
            {
                adjMat[i][j] = c;
                pred[i][j]=i;
            }
        }
    Graph::royFloydWarshall(adjMat, pred, inf);
    for(int i=0; i<n; ++i)
    {
        for(int j=0 ; j<n; ++j)
        {
            if(adjMat[i][j] != inf && i!=j)
                g<<adjMat[i][j]<<' ';
            else
                g<<"0 ";
        }

        g<<'\n';
    }

*/