#include<bits/stdc++.h>
using namespace std;

void BFS_Traversal(unordered_map<int, set<int>>&g, int src, int V, vector<int>&vis,vector<int>&ans)
{
    queue<int>q;
    // The task is to do Breadth First Traversal of this graph starting from 0.
    q.push(src); 
    vis[src]=1;

    while(!q.empty())
    {
        auto cur = q.front();
        ans.push_back(cur);
        q.pop();

        // explore neighbour
        for(auto nbr : g[cur])
        {
            if(vis[nbr]==0){
                vis[nbr]=1;
                q.push(nbr);
            }
        }
    }
}

vector<int> BFS(int V, vector<pair<int, int>> edges)
{
    vector<int>ans; // bfs traversal for graph
    // unordered_map<int, vector<int>>g; we did not take vector because we want to visit node in 
    // sorted order
    unordered_map<int, set<int>>g; 
    vector<int>vis(V,0); // no. of vetices
    for(auto &e : edges){
        g[e.first].insert(e.second);
        g[e.second].insert(e.first);
    }
    
    // handle for disconnected graphs as well
    for(int i=0;i<V;i++){
        if(vis[i]==0){
            BFS_Traversal(g,i,V,vis,ans);
        }
    }
    return ans;
}

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == NULL)
            return node;

        unordered_map<Node*, Node*> mp;
        queue<Node*> q;

        q.push(node);
        mp[node] = new Node(node->val); // map's key is old node and value is clone counter parts of that node

        while (!q.empty()) {
            Node* cur = q.front();
            q.pop();

            for (auto& nbr : cur->neighbors) {
                if (mp.find(nbr) == mp.end()) { //copy not present means lets create the copy for this neighbor also
                    mp[nbr] = new Node(nbr->val);
                    q.push(nbr);
                }
                // Establish new connection for new graph
                mp[cur]->neighbors.push_back(mp[nbr]); // have to update the neighbours for the clone counter parts as well
            }
        }
        return mp[node];
    }
};

#include<bits/stdc++.h>
using namespace std;

void dfs(int src, unordered_map<int, vector<int>>g, vector<int>&vis, vector<int>&dfsForComponent)
{
    vis[src] = 1;
    dfsForComponent.push_back(src);
    for(auto &x : g[src])
    {
        if(vis[x] == 0)
        {
            dfs(x,g,vis,dfsForComponent);
        }
    }
}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)
{
    vector<int>vis(V,0);
    vector<vector<int>>ans; // max connected components =  when all are single
    
    unordered_map<int, vector<int>>g;
    for(auto &e : edges){
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }
    
    for(int i=0;i<V;i++)
        if(vis[i]==0){
            vector<int>dfsForComponent;
            dfs(i,g,vis,dfsForComponent);
            ans.push_back(dfsForComponent);
        }
    return ans;
}

class Solution {
public:
    void dfs(Node* node, unordered_map<Node*, Node*> &mp) {
        Node* copy = new Node(node->val);
        mp[node] = copy; // map's key is old node and value is clone counter parts of that node

        for (auto nbr : node->neighbors) {
            if (mp.find(nbr) == mp.end()) {
                dfs(nbr, mp);
            }
            copy->neighbors.push_back(mp[nbr]); // have to update the neighbours for the clone counter parts as well
        }
    }

    Node* cloneGraph(Node* node) {
        if (node == NULL) return NULL;
        if (node->neighbors.size() == 0) {
            Node* clone = new Node(node->val);
            return clone;
        }
        unordered_map<Node*, Node*> mp;
        dfs(node, mp);
        return mp[node];
    }
};

class Solution {
public:
    
    bool checkForCycle(int src, vector<int>& vis, vector<vector<int>>& adj) {
        
        queue<pair<int,int>>q; // {node, parent}
        q.push({src, -1});
        vis[src] = 1;
        
        while(!q.empty()) {
            int node  = q.front().first;
            int parent = q.front().second;
            q.pop(); 
            
            for (auto &nbr: adj[node]) {
                if (!vis[nbr]) {
                    vis[nbr] = 1;
                    q.push({nbr, node});
                } else if (parent != nbr) {
				    // already visited but not a parent node
                    // visited nbr is not equal to parent, it means 
                    // we have node which is adjacent of node but visited previously via some other node.  
                    return true;
                }
            }
        }
        return false;
    }   
    
    bool isCycle(vector<vector<int>>& adj) {
        int n = adj.size();
        vector<int>vis(n,0);
        
        for(int i=0;i<n;i++) { // check for all the components
            if(!vis[i]) {
                if (checkForCycle(i, vis, adj)) return true; // yes, cycle exist
            }
        }
        return false; 
    }
};

class Solution {
public:
    
    bool checkForCycle(int src, int parent, vector<int>& vis, vector<vector<int>>& adj) {
        
        vis[src] = 1; // marking this as visited
        
        // iterate through all its neighbours
        for(auto &nbr : adj[src]) {
            if(!vis[nbr]) {
                if (checkForCycle(nbr, src, vis, adj)) return true;
            } else if (parent != nbr) {
				// already visited but not a parent node
                return true;
            }
        }
        return false;
    }   
    
    bool isCycle(vector<vector<int>>& adj) {
        int n = adj.size();
        vector<int>vis(n,0);
        
        for(int i=0;i<n;i++) { // check for all the components
            if(!vis[i]) {
                // taking parent for new starting node of a component as -1
                if (checkForCycle(i, -1, vis, adj)) return true; // yes, cycle exist
            }
        }
        return false; 
    }
};

int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) 
{  
    unordered_map<int, vector<int>>g;
    vector<int>indegree(n+1,0);
    for(auto &e : edges){
        g[e.first].push_back(e.second); // directed graph
        indegree[e.second]++;
    }
    queue<int>q;    
    for(int i=1;i<=n;i++){
        if(indegree[i]==0)
            q.push(i);
    }

    int cnt=0;
    while(!q.empty())
    {
        auto cur = q.front();
        q.pop();
        cnt++;
        for(auto &nbr : g[cur]){
            indegree[nbr]--;
            if(indegree[nbr]==0)
                q.push(nbr);
        }
    }
    if(cnt==n) return false;
    return true; 
}

#include<bits/stdc++.h>
using namespace std;

bool checkForCycle(int node, unordered_map<int, vector<int>>&g, vector<int>&vis, vector<int>&dfsvis)
{
    vis[node] = 1;
    dfsvis[node] = 1;
    for (auto it : g[node]) 
    {
        if(!vis[it]) 
        {
            if(checkForCycle(it, g, vis, dfsvis))
                return true;
        } 
        else if (dfsvis[it]) 
            return true;
    }
    dfsvis[node] = 0; // make unvisited 
    return false;
}

int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) 
{  
    unordered_map<int, vector<int>>g;
    for(auto &e : edges){
        g[e.first].push_back(e.second); // directed graph
    }
    
    vector<int> vis(n+1, 0);
    vector<int> dfsvis(n+1, 0);
    for (int i=1;i<=n;i++)
    {
        if (!vis[i])
        {
            if (checkForCycle(i, g, vis, dfsvis))
                 return true;;
        }
    }
    return false;
}

#include<bits/stdc++.h>
using namespace std;

vector<int> topologicalSort(vector<vector<int>> &edges, int n, int e)  {
    
    unordered_map<int, vector<int>>g;
    vector<int>indegree(n,0);
    for(auto &e : edges){
        g[e[0]].push_back(e[1]); // directed graph
        indegree[e[1]]++;
    }
    queue<int>q;    
    for(int i=0;i<n;i++){
        if(indegree[i]==0)
            q.push(i);
    }

    vector<int>topo;
    while(!q.empty())
    {
        auto cur = q.front();
        q.pop();
        topo.push_back(cur);
        for(auto &nbr : g[cur]){
            indegree[nbr]--;
            if(indegree[nbr]==0)
                q.push(nbr);
        }
    }
    return topo;
}

void dfs(int node, vector<int>&vis, stack<int>&st, unordered_map<int, vector<int>>&g) {
    
    vis[node] = 1;
    for (auto it: g[node]) {
        if (!vis[it]) {
            dfs(it, vis, st, g);
        }
    }
    st.push(node); // important line
}

vector<int> topologicalSort(vector<vector<int>> &edges, int n, int e)  {
    
    unordered_map<int, vector<int>>g;
    for(auto &e : edges){
        g[e[0]].push_back(e[1]); // directed graph
    }
    
    stack<int>st; // stack stores toposort 
    vector<int>vis(n, 0);
    for (int i = 0; i < n; i++){
        if (vis[i] == 0) {
            dfs(i, vis, st, g);
        }
    }
    
    vector<int>topo;
    while (!st.empty()) {
        topo.push_back(st.top());
        st.pop();
    }
    return topo;
}

// Acyclic/Linear - yes a bipartite graph 
// Cyclic - even length (yes a bipartite graph)
// Cyclic - odd length (Not a bipartite graph)
class Solution {
public:
    
    bool DFS(int src, int col, vector<vector<int>>& g, vector<int>& color) {
        color[src] = col;

        // traverse adjacent nodes
        for (auto& nbr : g[src]) {
            // if uncoloured
            if (color[nbr] == -1) {
                if (DFS(nbr, !col, g, color) == false)
                    return false;
            } 
            // if previously coloured and have the same colour as the parent
            else if (color[nbr] == color[src])
                return false;
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& g) {
        int n = g.size(); // no. of nodes
        vector<int> color(n, -1); // color array works as the visited array for the DFS, initially no one is coloured

        // The graph may not be connected, meaning there may be two nodes u and
        // v such that there is no path between them. so check for all the components of graph.
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (DFS(i, 0, g, color) == false) { 
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    bool BFS(int src, vector<vector<int>>& g, vector<int>& color) {
        int n = g.size(); // no. of nodes

        queue<int> q;
        q.push(src);
        color[src] = 0; // initial color for src

        while (!q.empty()) {
            auto cur = q.front();
            q.pop();

            for (auto& nbr : g[cur]) {
                // if it is unvisited
                if (color[nbr] == -1) {
                    color[nbr] = color[cur] ? 0 : 1;
                    q.push(nbr);
                } 
                // if previously coloured and have the same colour as the parent
                else if (color[nbr] == color[cur])
                    return false;
            }
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& g) {
        int n = g.size(); // no. of nodes
        vector<int> color(n, -1);

        // The graph may not be connected, meaning there may be two nodes u and
        // v such that there is no path between them. so check for all the components of graph.
        for (int i = 0; i < n; i++) {

            if (color[i] == -1) {
                if (BFS(i, g, color) == false) { 
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    void bfs(vector<vector<char>>& grid, vector<vector<int>>& vis, int i, int j, int m, int n) {
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, -1, 0, 1};

        queue<pair<int, int>> q;
        q.push({i, j}); // source
        vis[i][j] = 1;

        while (!q.empty()) {
            auto p = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) // check for all four directions
            {
                int nr = p.first + dx[i];
                int nc = p.second + dy[i];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && vis[nr][nc] == 0 && grid[nr][nc] == '1') {
                    vis[nr][nc] = 1;
                    q.push({nr, nc}); // push until we are able to find the land or connected components
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));

        int components = 0; // number of islands
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 0 && grid[i][j] == '1') {
                    bfs(grid, vis, i, j, m, n);
                    components++;
                }
            }
        }
        return components;
    }
};

class Solution {
public:

    void dfs(int i, int j, int m, int n, vector<vector<int>>& vis, vector<vector<char>>& grid) {
        if (i < 0 || i >= m || j < 0 || j >= n)
            return;
        if (vis[i][j] == 1 || grid[i][j] == '0')
            return;
        vis[i][j] = 1;

        dfs(i - 1, j, m, n, vis, grid);
        dfs(i, j - 1, m, n, vis, grid);
        dfs(i + 1, j, m, n, vis, grid);
        dfs(i, j + 1, m, n, vis, grid);
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));

        int components = 0; // number of islands
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == 0 && grid[i][j] == '1') {
                    dfs(i, j, m, n, vis, grid);
                    components++;
                }
            }
        }
        return components;
    }
};

// matrix of 0, 1 given
// 1 - there is an edge
// 0 - there is no edge 
class Solution {
public:
    void DFS(int src, vector<int>& vis, unordered_map<int, vector<int>>& g) {
        vis[src] = 1; // mark as visited

        // iterate all the neighbours
        for (auto& nbr : g[src]) {
            if (!vis[nbr]) {
                DFS(nbr, vis, g);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        unordered_map<int, vector<int>> g; // graph (adjacency list)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    // no need to add reverse edge because matrix loop will take care of this.
                    g[i + 1].push_back(j + 1); 
                }
            }
        }
        vector<int> vis(n + 1, 0); // 1 based node values

        int components = 0;
        for (int i = 1; i <= n; i++) { // loop from (1 -> n) instead of (0 to n-1)
            if (!vis[i]) {
                DFS(i, vis, g);
                components++;
            }
        }
        return components;
    }
};

// Follow - up : Without creating unordered map, use same matrix as graph. 
class Solution {
public:
    void dfs(int src, vector<int>& vis, vector<vector<int>>& isConnected) {
        vis[src] = 1;
        for (int j = 0; j < isConnected.size(); j++) {
            if (isConnected[src][j] == 1 && !vis[j]) {
                dfs(j, vis, isConnected);
            }
        }
    }

    // Bidirectional graph is given => isConnected[i][j] == isConnected[j][i]
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size(); // nxn matrix
        vector<int> vis(n, 0);

        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i, vis, isConnected);
                components++;
            }
        }
        return components;
    }
};

class Solution {
public:

	// Function to find out minimum steps Knight needs to reach target position.
    // nxn chessboard given - Using BFS
	int minStepToReachTarget(vector<int>&KnightPos, vector<int>&TargetPos, int n)
	{
	    // initial position
	    int x1 = KnightPos[0];
	    int y1 = KnightPos[1];
	    // target position
	    int x2 = TargetPos[0];
	    int y2 = TargetPos[1];
	    if(x1 == x2 and y1 == y2) return 0; // already at target position

	    vector<vector<int>>vis(n+1, vector<int>(n+1, 0));
	    /*
	      // 8 places possible where Knight can move 
	              1  2
                  🟩🟩🟩
              8 🟩  🟩  🟩 3 
                🟩🟩🟥🟩🟩 
              7 🟩  🟩  🟩 4
                  🟩🟩🟩
                  6   5
	    */
        vector<vector<int>>dir = {{-2,-1},{-2,1},
                                  {-1,2}, {1,2},   
                                  {2,-1},{2,1},
                                  {-1,-2},{1,-2}};
        
	    queue<pair<int,int>>q;
	    q.push({x1-1,y1-1}); // convert into 0th based indexing 
	    vis[x1-1][y1-1]=1; // mark it as visited
	    
	    int steps=0;
	    while(!q.empty())
	    {
	        int sz = q.size();
	        while(sz--)
	        {
	            auto cur = q.front();
	            int i = cur.first;
	            int j = cur.second;
	            q.pop();
	            
	            if(x2-1==i and y2-1==j) return steps;
	            for(auto &d : dir)
	            {
	                int ni = i+d[0];
	                int nj = j+d[1];
	                if(ni>=0 and ni<n and nj>=0 and nj<n and vis[ni][nj]==0){
	                    q.push({ni,nj});
	                    vis[ni][nj]=1;
	                }
	            }
	        }
	        steps++;
	    }
	    return -1;
	}
};

#include<bits/stdc++.h>
using namespace std;

void toposort_dfs(int node, stack<int> &st, vector<int> &vis, vector<vector<int>>&g) {
    vis[node] = 1; 
    for(auto it: g[node]) {
        if(!vis[it]) {
            toposort_dfs(it, st, vis, g); 
        }
    }
    st.push(node); 
}

void revDfs(int node, vector<int> &vis, vector<vector<int>>&transpose, vector<int>&ans) {
    
    ans.push_back(node);
    vis[node] = 1; 
    for(auto it: transpose[node]) {
        if(!vis[it]) {
            revDfs(it, vis, transpose, ans); 
        }
    }
}

vector<vector<int>> stronglyConnectedComponents(int n, vector<vector<int>>&edges)
{
    // two graphs one is normal and other is transpose 
    vector<vector<int>>g(n,vector<int>{});
    vector<vector<int>>transpose(n, vector<int>{});
    for(auto &e:edges){
        g[e[0]].push_back(e[1]);
    }
    
    vector<int>vis(n,0);
    stack<int>st;
    // step-1
    for(int i=0;i<n;i++){
        if(!vis[i])
            toposort_dfs(i, st, vis, g);
    }
    
    // step-2
    for(auto &e:edges){
        transpose[e[1]].push_back(e[0]);
    }
    
    // step-3
    vis = vector<int>(n,0);
    vector<vector<int>>fans;// final answer
    while(!st.empty())
    {
        int i = st.top();
        st.pop();
        if(!vis[i])
        {
            vector<int>ans;
            revDfs(i, vis, transpose, ans);
            fans.push_back(ans);
        }    
    }
    return fans;
}

- Because in that case we will be doing unneccessary iterations or occurences/exploration of paths and we are going to each
path and finding the minimal of all. but in case of priority queue we will be only taking the path with only minimal distances.
- using a queue kind of doing brute force and it will take lots of time. 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>ppi; // {dist, node}

class Solution{
public:

    // using "unordered_map<int, vector<pair<int,int>>>graph" is also equivalent to "vector<vector<pair<int, int >>>graph"
	// sometimes you will be given edges in this way -> "vec -> x->y,wt" i.e vector<vector<int>>&vec, then you need to create a graph in this case.
	// undirected graph x --> y, wt
    // unordered_map<int, vector<pair<int,int>>>g; 
    // for(auto&x:vec){
    //    g[x[0]].push_back({x[1], x[2]});
    //    g[x[1]].push_back({x[0], x[2]});
    // }
	vector <int> dijkstra(vector<vector<pair<int, int>>> &adj, int src) {
	    
        int n = adj.size(); // number of vertices
        priority_queue<ppi, vector<ppi>, greater<ppi>> pq; // min heap
        vector<int>distTo(n, INT_MAX);
       
        pq.push({0, src}); // dist, node
        distTo[src] = 0;
       
        while(!pq.empty())
        {
		    // Always pop node with minimum distance 
            int dist = pq.top().first;
            int node = pq.top().second; // current node
            pq.pop();
           
            for(auto &nbr : adj[node]) {
                int adjNode = nbr.first;
                int edgeWeight = nbr.second;
                if (dist + edgeWeight < distTo[adjNode]) {
                   distTo[adjNode] = dist + edgeWeight;
                   pq.push({distTo[adjNode], adjNode});
                }
            }
        }
        return distTo;
    } 
};

class Solution{
public:

	vector <int> dijkstra(vector<vector<pair<int, int>>> &adj, int src) {
	    
        int n = adj.size(); // number of vertices
        set<pair<int,int>>st; // {dist, node}
        vector<int>distTo(n, INT_MAX);
       
        st.insert({0, src}); // dist, node
        distTo[src] = 0;
       
        while(!st.empty())
        {
            auto it = *(st.begin());
            int dist = it.first;
            int node = it.second; // current node
            st.erase(it);
           
            for(auto &nbr : adj[node]) {
                int adjNode = nbr.first;
                int edgeWeight = nbr.second;
                
                if(dist + edgeWeight < distTo[adjNode]) {
                    // earse if it is existed
                    // it means someone reached this node in past previously, there is no point in keeping 
                    // that pair, e.g {dist, node} = {10, 5}, but now we have found {8, 5}, then remove {10,5}
                    if(distTo[adjNode] != INT_MAX) { 
                       st.erase({distTo[adjNode], adjNode}); // minor optimization
                    }
                    distTo[adjNode] = dist + edgeWeight;
                    st.insert({distTo[adjNode], adjNode});
                }
            }
        }
        return distTo;
    } 
};