//
//  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("dfs.in");
ofstream output("dfs.out");

class DisjointSets
{
    int nodes;
    int father[N];    //the vector that holds the representative of each node

public:
    DisjointSets(int nodes);
    void initialization(int node);      //creates each node as a subtree
    int reprezentative(int node);       //returns the representative of the component that contains it on the node
    void reunite(int node1, int node2, int height[]);     //joins the component that contains node1 with the one that contains node2
};

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

void DisjointSets::initialization(int nodes)
{
    for (int i = 1 ; i <= nodes; i++)
    {
        father[i] = 0;
    }
}

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

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

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

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

    void dfs(int node, bool visited[]);     //DFS traversal of the graph
    void outputAdj();       //display the vector of adjacent node vectors
    static bool sortByThird (const tpl &a, const tpl&b);    //sort the tuple vector that also contains the cost of the edges according to the third parameter (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 adapted to calculate the cost of traversing each node

    //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[]);     // Auxiliary DFS for the determination of biconnected components

    //PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
    void calculateIndegree(int indegree[]);       //auxiliary function of topological sorting for calculating the inner degree of each node
    vector<int> topSort(int indegree[], queue<int> queue_ts);      //topological sorting function

    //PROBLEMA HAVEL-HAKIMI
    bool graphExists (vector<int> degree_seq);      //the function that decides whether or not a sequence of numbers can represent a sequence of nodes of a graph
    void inputArray (vector<int> &degree_seq);

    //PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
    void inputApm(vector<tpl> &weight_edges);       //function that stores the input for the minimum cost spanning tree
    vector<Pair> apmUtil(vector<tpl> &weight_edges, int &weight);        //function that calculates the minimum cost spanning tree

    //PROBLEMA ALGORITMUL LUI DIJKSTRA INFOARENA: https://infoarena.ro/problema/dijkstra
    vector<int> dijkstra(int start);

    //PROBLEMA ALGORITMUL BELLMAN-FORD: https://infoarena.ro/problema/bellmanford
    bool bellmanFord(int start, vector<int> &dist);

    //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(vector<vector<int>> &dist);
    vector<vector<int>> RoyFloydUtil(vector<vector<int>> &dist);

    //PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
    void dfsUtilDiameter(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();     //determining the number of related components of the graph

    //PROBLEMA bfs INFORARENA: https://infoarena.ro/problema/bfs
    vector<int> bfs(int start);     //bfs adapted to calculate the cost of traversing each node, starting from a starting node

    //PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
    vector<vector<int>> biconnectedComponents();

    //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(int &weight);

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

    //PROBLEMA ALGORITMUL LUI DIJKSTRA INFOARENA: https://infoarena.ro/problema/dijkstra
    vector<int> calculateMinimumDistances();

    //PROBLEMA ALGORITMUL BELLMAN-FORD: https://infoarena.ro/problema/bellmanford
    bool negaticveCostCycleExists(vector<int> &dist);

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

    //PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
    vector<vector<int>> 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(int &counter);
};

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::addEdgesTree()
{
    int node1, node2;
    for(int i = 0 ; i < nodes; 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] = true;      //mark the current node as visited
    queue_bfs.push(node);
    cost[node] = 0;

    while (!queue_bfs.empty())
    {
        node = queue_bfs.front();       //take the node from the top of the queue
        queue_bfs.pop();

        for (int i = 0 ; i < adj[node].size() ; i++)        //go through all the adjacent nodes with node
            if ( !visited[adj[node][i]])        //if they are not visited
            {
                visited[adj[node][i]] = 1;          //mark them as visited
                queue_bfs.push(adj[node][i]);           //push into the queue
                cost[adj[node][i]] = cost[node] + 1;        //calculate the cost relative to his "parent"
            }
    }
    
    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;

    unsigned long int dim = adj[node].size();
    for ( int i = 0 ; i< dim ; i++)
    {
        child = adj[node][i];
        if (child != parent)
        {
            if (visited[child] == true)         //if his son has already been visited and is not the father of the current node, the edge (son, node) is a return edge
            {
                if(level[child] < low_level[node])low_level[node] = level[child];       //we update the value of low_level[node] if his son is higher than him (because we have a returning edge)
            }
            else        //if his son has not yet been visited, we continue DFS from the son
            {
                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];         //if the child has a lower return level than the node when returning from the call, we update low_level[node]

                if (low_level[child] >= level[node])        //node is the articulation point
                {
                    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};          //the level at which a node is
    int low_level[N] = {0};         //the minimum return level of a node
    bool visited[N] = {0};
    stack<pair<int, int>> component_node;
    vector<vector<int>> bcc;        //the vector that stores the biconnected components
    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++)        //push into the queue only the nodes with indegree 0
    {
        if (indegree[i] == 0)
            queue_ts.push(i);
    }

    while (!queue_ts.empty())       //as long as the queue is not empty, we extract the front node, subtract the degrees of the nodes adjacent to the front and add in the queue those nodes that have the indegree 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;        //queue in which we will add only the nodes that have the inner degree 0
    int indegree[N] ;       //the vector that holds the indegree of each node

    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)     //if all the remaining elements are 0, then a graph can be constructed
            return true;

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

        if (top > degree_seq.size())        //if the value of the first element is greater than the number of elements remaining, we cannot construct such a graph
            return false;

        for (int i = 0 ; i < degree_seq.size() ; i++)        //after removing the first element, subtract the degree of the remaining "nodes"
        {
            degree_seq[i]--;
            if(degree_seq[i] < 0)        //if negative numbers appear, we cannot construct a graph
                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;         //the vector that contains the degrees of a possible graph

    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 &weight)
{
    int height[N] = {0};
    sort(weight_edges.begin(), weight_edges.end(), sortByThird);        //we sort ascending the vector by cost

    DisjointSets djs(nodes);
    djs.initialization(nodes);         //we consider that each node represents a subtree

    int ctr = 0;        //the number of edges of the MST at a given time
    vector<Pair> apm;
    for (int i = 0 ; i < edges ; i++)
    {
        int n1 = get<0>(weight_edges[i]);           //for each iteration we choose the edge with minimum cost
        int n2 = get<1>(weight_edges[i]);

        int r1 = djs.reprezentative(n1);            //we check the representatives of the nodes incident to this edge
        int r2 = djs.reprezentative(n2);

        if (r1 != r2)           //if we have different representatives, the subtrees of which the nodes take part come together; otherwise, we ignore the edge, because it would generate a cycle in MST
        {
            apm.push_back(make_pair(n1, n2));
            ctr++;
            weight += get<2>(weight_edges[i]);
            djs.reunite(n1, n2, height);

            if  (ctr == nodes - 1)          //a tree can have a maximum of n-1 edges between n nodes; so if we find n-1 edges we can stop the search
                break;
        }
    }

    return apm;
}

vector<Pair> Graph::apm(int &weight)
{
    vector<tpl> weight_edges;

    inputApm(weight_edges);
    return apmUtil(weight_edges, weight);
}

void Graph::disjoint()
{
    int height[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);
        else
        {
            int r1 = djs.reprezentative(x);
            int r2 = djs.reprezentative(y);

            if(r1 != r2)
                output << "NU\n";
            else output << "DA\n";
        }
    }
}

vector<int> Graph::dijkstra(int start)
{
    vector<int> dist;       //the vector that stores the minimum distance from the start node to the other nodes
    priority_queue<Pair, vector<Pair>, greater<Pair>> queue_adj;        //queue in which we store the adjacent nodes and the costs of the adjacent edges of the currently visited node in order to have the order of traversal
                                                                        //we will first retain the cost and then the adjacent node so that we can easily obtain at each iteration the node that has the associated edge of minimum cost

    dist.assign(nodes + 1, INF);

    queue_adj.push(make_pair(0, start));        //for the start node we have the cost 0 to get to it
    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++)         //for all adjacent nodes of node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])          //we check if for the adjacent nodes we find a shorter path through node than the ones already traversed
            {
                dist[child] = dist[node] + weight;
                queue_adj.push(make_pair(dist[child], child));

            }
        }
    }

    replace(dist.begin(), dist.end(), INF, 0);

    return dist;
}

vector<int> Graph::calculateMinimumDistances()
{
    addEdgesDgWeight();
    return dijkstra(1);
}

bool Graph::bellmanFord(int start, vector<int> &dist)
{
    int len[N] = {0};       //the vector that stores the length of a path from the source to another node
    queue<int> queue_bf;        //the queue that stores the nodes whose minimum distance has changed

    dist.assign(nodes + 1, INF);

    dist[start] = 0;        //for the start node we have the cost 0 to get to it
    queue_bf.push(start);

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

        for (int i = 0 ; i < adj_weight[node].size() ; i++)         //for all adjacent nodes of node
        {
            int child = get<0>(adj_weight[node][i]);
            int weight = get<1>(adj_weight[node][i]);

            if (dist[node] + weight < dist[child])          //we check if for the adjacent nodes we find a shorter path through node than the ones already traversed
            {
                len[child] = len[node] + 1;
                if (len[child] == nodes)            //if we obtain a length greater than or equal to n, it means that in the graph there is a negative cycle
                {
                    return true;
                }
                dist[child] = dist[node] + weight;
                queue_bf.push(child);
            }
        }
    }

    return false;
}

bool Graph::negaticveCostCycleExists(vector<int> &dist)
{
    addEdgesDgWeight();
    return bellmanFord(1, dist);
}


bool Graph::bfsMaxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[], bool visited[])
{
    for (int i = 1 ; i <= nodes ; i++)
        visited[i] = false;

    queue<int> q;
    q.push(src);
    visited[src] = true;        //mark the current node as visited
    parent[src] = 0;

    while (!q.empty())
    {
        int node = q.front();       //we take the first element from the tail
        q.pop();

        for (int i = 0 ; i < adj_capacity[node].size() ; i++)        //traverse all nodes adjacent to the current node
        {
            int j = get<0>(adj_capacity[node][i]);
            if (!visited[j] && residualGraph[node][j] > 0)
            {
                if (j == dst)           //if we found a path from source to destination, we stop with 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;        //we create a residual graph that we initialize with the capacity values ​​from the original graph
                                             //residualGraph[i][j] -> the capacity of the arc from i to j, if there is any
    bool visited[N] = {0};
    int parent[nodes + 1];          //the vector used to store the path from source to destination
    int max_flow = 0;           //initially we have no flow

    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)) {      //while we have a path from source to destination
                                                                        //we search for the minimum residual capacity of each arc along the road found by 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]);
        }

        for (int i = dst ; i != src ; i = parent[i])           //we modify the residual values ​​of the direct and inverse arcs that are on the path found by bfs
        {
            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);
}

vector<vector<int>> Graph::RoyFloydUtil(vector<vector<int>> &dist)
{
    for (int k = 1 ; k <= nodes ; k++)          //we consider one node at a time as an intermediate
        for (int i = 1 ; i <= nodes ; i++)          //we consider one node at a time as a source
            for (int j = 1 ; j <= nodes ; j++)          //we consider one node at a time as a destination
                if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) {       //we change the distance
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
                else if (i == j)
                {
                    dist[i][j] = 0;
                }

    return dist;
}

void Graph::inputRoyFloyd(vector<vector<int>> &dist)
{
    dist.resize(nodes + 1, vector<int> (nodes + 1, 0));
    
    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;
        }
    }
}

vector<vector<int>> Graph::RoyFloyd()
{
    vector<vector<int>> dist;
    inputRoyFloyd(dist);
    return RoyFloydUtil(dist);
}

void Graph::dfsUtilDiameter(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];
            }
            dfsUtilDiameter(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;

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

int Graph::diameter()
{
    addEdgesTree();
    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<Pair> vectorEdges[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;

    for (int i = 0 ; i < edges ; i++)
    {
        int x, y;
        input >> x >> y;
        vectorEdges[x].push_back(make_pair(y,i));
        vectorEdges[y].push_back(make_pair(x,i));
    }

    for (int i = 1 ; i <= nodes ; i++)
    {
        if (vectorEdges[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 (!vectorEdges[node].empty())       //if the current node still has adjacent nodes
        {
            Pair p = vectorEdges[node].back();
            vectorEdges[node].pop_back();

            int adj_node = get<0>(p);
            int edge_code = get<1>(p);

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

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(int &counter)
{
    /*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;
    counter = 0;        //stores the number of edges for 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
            {
                counter = ++result;
                result_nodes.push_back(make_pair(u, pairU[u]));
            }
        }
    }

    return result_nodes;
}

int main(int argc, const char * argv[])
{
    int nodes, edges;
    input >> nodes >> edges;
    
    Graph g(nodes, edges);
    output << g.connectedComponents();
}