// N queens 

class Solution {
public:

    bool isSafe(int row , int col ,vector<string> board , int n )
    {
        int checkr = row ;
        int checkc = col ;
        while( checkr >=0 && checkc>=0)
        {
            if(board[checkr][checkc]=='Q')
            {
                return false ;
            }
            checkr --; checkc --;    
        }
        int tc = col ;
        while(tc>=0)
        {
             if(board[row][tc]=='Q')
            {
                return false ;
            }
            tc--;
        }
        checkr = row ;
        checkc = col ;
        while( checkr <n && checkc>=0)
        {
            if(board[checkr][checkc]=='Q')
            {
                return false ;
            }
            checkr ++; checkc --;    
        }
        return true ;
    }

    void solve(int col ,vector<string> &board ,   vector<vector<string>> &answer , int n )
    {

        if (col == n )
        {
            answer.push_back(board) ;
            return ;
        }
       for(int row =0 ; row<n ; row++)
       {
        if(isSafe(row , col , board , n))
        {
            board[row][col]= 'Q';
            solve(col+1 , board , answer , n );
            board[row][col]= '.';
        }
       }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> answer ;
        vector<string> board(n) ;
        string s(n , '.') ;
        for(int i = 0 ; i <n ;i++)
        {
            board[i] = s ;
        }
        solve(0, board , answer , n);
        return answer;
        
    }
};

// activity seq 

class Solution {
public:
    static bool compare(vector<int> v1 , vector<int> v2 )
    {
        if (v1[1] == v2[1]) return v1[0]<v2[0];
        return v1[1]<v2[1] ;
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), compare);

    int i = 0 ;
    int j = 1 ;
    int c = 1 ;
    int n = intervals.size();

    while(j<n)
    {
        if(intervals[i][1] <= intervals[j][0])
        {
            c++;
            i = j ;
            j++ ; 
        }
        else
        {
            j++ ;
        }
    }

        return n - c ;
    }
};

// LCS 

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

class Solution {
public:

    int solve(string s1, string s2, int i, int j, vector<vector<int>>& vec) {
        if (i == s1.length() || j == s2.length()) {
            return 0;
        }
        if (vec[i][j] != -1) {
            return vec[i][j];
        }
        int ans = 0;
        if (s1[i] == s2[j]) {
            ans = 1 + solve(s1, s2, i + 1, j + 1, vec);
        }
        else {
            ans = max(solve(s1, s2, i + 1, j, vec), solve(s1, s2, i, j + 1, vec));
        }
        return vec[i][j] = ans;
    }

    int longestCommonSubsequence(string text1, string text2) {
        int rows = text1.length();
        int cols = text2.length();
        vector<vector<int>> vec(rows, vector<int>(cols, -1));

        return solve(text1, text2, 0, 0, vec);
    }
};

//eulers 

#include <unordered_map>
#include<queue>
#include<list>


bool iscyclicBFS(int src,    unordered_map<int,bool> &visited,   unordered_map<int,list<int>> adj){
     unordered_map<int,int> parent;
    parent[src]=-1;
    visited[src]=1;
    queue<int> q;
    q.push(src);
    while(!q.empty()){
        int front = q.front();
        q.pop();
        
        for(auto neighbour: adj[front]){
            if(visited[neighbour]==true && neighbour!=parent[front]){
                return true;
            }
            else if(!visited[neighbour]){
                q.push(neighbour);
                visited[neighbour]=1;
                parent[neighbour]=front;
            }
        }
    }
    return false;
}

bool iscyclicDFS(int node,int parent, unordered_map<int,bool> &visited, unordered_map<int,list<int>> &adj){
    visited[node]=true;
    for(auto neighbour: adj[node]){
        if(!visited[neighbour]){
            bool cycledetected=iscyclicDFS(neighbour, node,visited,adj);
            if(cycledetected)
                return true;
        }
        else if(neighbour != parent){
           //cycle present
            return true;
        }
    }
 return false;
}

string cycleDetection (vector<vector<int>>& edges, int n, int m)
{
    // create adjacency list
    unordered_map<int,list<int>> adj;
    for(int i=0;i<m;i++){
        int u = edges[i][0];
        int v = edges[i][1];
        
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    //to handle disconnected components 
        unordered_map<int,bool> visited;
    for(int i=0;i<n;i++){
        if(!visited[i]){
            // bool ans = iscyclicBFS(i,visited,adj);
            bool ans = iscyclicDFS(i,-1,visited,adj);
            if(ans == 1){
                return "Yes";
            }
                
        }
    }
    return "No";
}