/*

// Job sequencing

#include <algorithm>
#include <iostream>
using namespace std;

struct Job {

    char id;
    int dead;
    int profit; 
               
};

bool comparison(Job a, Job b)
{
    return (a.profit > b.profit);
}

void printJobScheduling(Job arr[], int n)
{
    sort(arr, arr + n, comparison);

    int result[n]; 
    bool slot[n]; 
    for (int i = 0; i < n; i++)
        slot[i] = false;
    for (int i = 0; i < n; i++) {
        for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

            if (slot[j] == false) {
                result[j] = i; // Add this job to result
                slot[j] = true; // Make this slot occupied
                break;
            }
        }
    }

    for (int i = 0; i < n; i++)
        if (slot[i])
            cout << arr[result[i]].id << " ";
}

int main()
{
    Job jj;
    Job arr[100];
    for(int i=0;i<5;i++)
    {
        cin>>jj.id>>jj.dead>>jj.profit;
        arr[i]={jj.id,jj.dead,jj.profit};

    }
    // Job arr[] = { { 'a', 2, 100 },
    //             { 'b', 1, 19 },
    //             { 'c', 2, 27 },
    //             { 'd', 1, 25 },
    //             { 'e', 3, 15 } };
    
    int n = 5;
    cout << "Following is maximum profit sequence of jobs "
            "\n";

    printJobScheduling(arr, n);
    return 0;
}



// Activityy Selection

#include <bits/stdc++.h>

using namespace std; 

struct Activity 
{ 
    int start, finish; 
}; 

// This function is used for sorting activities according to finish time 
bool Sort_activity(Activity s1, Activity s2) 
{ 
    return (s1.finish< s2.finish); 
} 

/*  Prints maximum number of activities that can
    be done by a single person or single machine at a time. 
*/
void print_Max_Activities(Activity arr[], int n) 
{ 
    // Sort activities according to finish time 
    sort(arr, arr+n, Sort_activity); 

    cout<< "Following activities are selected \n"; 

    // Select the first activity
    int i = 0; 
    cout<< "(" <<arr[i].start<< ", " <<arr[i].finish << ")\n"; 

    // Consider the remaining activities from 1 to n-1 
    for (int j = 1; j < n; j++) 
    { 
        // Select this activity if it has start time greater than or equal
        // to the finish time of previously selected activity
        if (arr[j].start>= arr[i].finish) 
        {    
            cout<< "(" <<arr[j].start<< ", "<<arr[j].finish << ") \n"; 
            i = j; 
        } 
    } 
} 

// Driver program 
int main() 
{ 
    Activity arr[6];
    for(int i=0; i<6; i++)
    {
        cout<<"Enter the start and end time of "<<i+1<<" activity \n";
        cin>>arr[i].start>>arr[i].finish;
    }

    print_Max_Activities(arr, N); 
    return 0; 
}


// C++ program to solve knapsack problem using
// branch and bound
#include <bits/stdc++.h>
using namespace std;

// Structure for Item which store weight and corresponding
// value of Item
struct Item
{
 float weight;
 int value;
};

// Node structure to store information of decision
// tree
struct Node
{
 // level --&gt; Level of node in decision tree (or index
 //    in arr[]
 // profit --&gt; Profit of nodes on path from root to this
 //   node (including this node)
 // bound ---&gt; Upper bound of maximum profit in subtree
 //   of this node/
 int level, profit, bound;
 float weight;
};

// Comparison function to sort Item according to
// val/weight ratio
bool cmp(Item a, Item b)
{
 double r1 = (double)a.value / a.weight;
 double r2 = (double)b.value / b.weight;
 return r1 > r2;
}



// knapsack Using branch and bound 

int bound(Node u, int n, int W, Item arr[])
{
 // if weight overcomes the knapsack capacity, return
 // 0 as expected bound
 if (u.weight >= W)
  return 0;

 // initialize bound on profit by current profit
 int profit_bound = u.profit;

 // start including items from index 1 more to current
 // item index
 int j = u.level + 1;
 int totweight = u.weight;

 // checking index condition and knapsack capacity
 // condition
 while ((j < n) && (totweight + arr[j].weight <= W))
 {
  totweight += arr[j].weight;
  profit_bound += arr[j].value;
  j++;
 }

 // If k is not n, include last item partially for
 // upper bound on profit
 if (j < n)
  profit_bound += (W - totweight) * arr[j].value /
          arr[j].weight;

 return profit_bound;
}

// Returns maximum profit we can get with capacity W
int knapsack(int W, Item arr[], int n)
{
 // sorting Item on basis of value per unit
 // weight.
 sort(arr, arr + n, cmp);

 // make a queue for traversing the node
 queue<Node> Q;
 Node u, v;

 // dummy node at starting
 u.level = -1;
 u.profit = u.weight = 0;
 Q.push(u);

 // One by one extract an item from decision tree
 // compute profit of all children of extracted item
 // and keep saving maxProfit
 int maxProfit = 0;
 while (!Q.empty())
 {
  // Dequeue a node
  u = Q.front();
  Q.pop();

  // If it is starting node, assign level 0
  if (u.level == -1)
   v.level = 0;

  // If there is nothing on next level
  if (u.level == n-1)
   continue;

  // Else if not last node, then increment level,
  // and compute profit of children nodes.
  v.level = u.level + 1;

  // Taking current level's item add current
  // level's weight and value to node u's
  // weight and value
  v.weight = u.weight + arr[v.level].weight;
  v.profit = u.profit + arr[v.level].value;

  // If cumulated weight is less than W and
  // profit is greater than previous profit,
  // update maxprofit
  if (v.weight <= W && v.profit > maxProfit)
   maxProfit = v.profit;

  // Get the upper bound on profit to decide
  // whether to add v to Q or not.
  v.bound = bound(v, n, W, arr);

  // If bound value is greater than profit,
  // then only push into queue for further
  // consideration
  if (v.bound > maxProfit)
   Q.push(v);

  // Do the same thing, but Without taking
  // the item in knapsack
  v.weight = u.weight;
  v.profit = u.profit;
  v.bound = bound(v, n, W, arr);
  if (v.bound > maxProfit)
   Q.push(v);
 }

 return maxProfit;
}

// driver program to test above function
int main()
{
 int W = 10; // Weight of knapsack
 Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
    {5, 95}, {3, 30}};
 int n = sizeof(arr) / sizeof(arr[0]);

 cout << "Maximum possible profit = "
  << knapsack(W, arr, n);

 return 0;
}


// knapsack using DP

// CPP code for Dynamic Programming based
// solution for 0-1 Knapsack problem
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }

// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n)
{
 int i, w;
 int K[n + 1][W + 1];

 // Build table K[][] in bottom up manner
 for (i = 0; i <= n; i++) {
  for (w = 0; w <= W; w++) {
   if (i == 0 || w == 0)
    K[i][w] = 0;
   else if (wt[i - 1] <= w)
    K[i][w] = max(val[i - 1] +
     K[i - 1][w - wt[i - 1]], K[i - 1][w]);
   else
    K[i][w] = K[i - 1][w];
  }
 }

 // stores the result of Knapsack
 int res = K[n][W];
 cout<< res << endl;
 
 w = W;
 for (i = n; i > 0 && res > 0; i--) {
  
  // either the result comes from the top
  // (K[i-1][w]) or from (val[i-1] + K[i-1]
  // [w-wt[i-1]]) as in Knapsack table. If
  // it comes from the latter one/ it means
  // the item is included.
  if (res == K[i - 1][w])
   continue; 
  else {

   // This item is included.
   cout<<" "<<wt[i - 1] ;
   
   // Since this weight is included its
   // value is deducted
   res = res - val[i - 1];
   w = w - wt[i - 1];
  }
 }
}

// Driver code
int main()
{
 int val[] = { 60, 100, 120 };
 int wt[] = { 10, 20, 30 };
 int W = 50;
 int n = sizeof(val) / sizeof(val[0]);
 
 printknapSack(W, wt, val, n);
 
 return 0;
}


// matrix chain multiplication using recursion

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

// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1 . . . n
int MatrixChainOrder(int p[], int i, int j)
{
 if (i == j)
  return 0;
 int k;
 int mini = INT_MAX;
 int count;

 // Place parenthesis at different places
 // between first and last matrix, 
 // recursively calculate count of multiplications 
 // for each parenthesis placement 
 // and return the minimum count
 for (k = i; k < j; k++) 
 {
  count = MatrixChainOrder(p, i, k)
    + MatrixChainOrder(p, k + 1, j)
    + p[i - 1] * p[k] * p[j];

  mini = min(count, mini);
 }

 // Return minimum count
 return mini;
}

// Driver Code
int main()
{
 int arr[] = { 1, 2, 3, 4, 3 };
 int N = sizeof(arr) / sizeof(arr[0]);

 // Function call
 cout << "Minimum number of multiplications is "
  << MatrixChainOrder(arr, 1, N - 1);
 return 0;
}



// N-Queen
#include<iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << board[i][j] << " ";
         cout << endl;
   }
}
bool isValid(int board[N][N], int row, int col) {
   for (int i = 0; i < col; i++) //check whether there is queen in the left or not
      if (board[row][i])
         return false;
   for (int i=row, j=col; i>=0 && j>=0; i--, j--)
      if (board[i][j]) //check whether there is queen in the left upper diagonal or not
         return false;
for (int i=row, j=col; j>=0 && i<N; i++, j--)
      if (board[i][j]) //check whether there is queen in the left lower diagonal or not
         return false;
   return true;
}
bool solveNQueen(int board[N][N], int col) {
   if (col >= N) //when N queens are placed successfully
      return true;
   for (int i = 0; i < N; i++) { //for each row, check placing of queen is possible or not
      if (isValid(board, i, col) ) {
         board[i][col] = 1; //if validate, place the queen at place (i, col)
         if ( solveNQueen(board, col + 1)) //Go for the other columns recursively
            return true;
         board[i][col] = 0; //When no place is vacant remove that queen
      }
   }
   return false; //when no possible order is found
}
bool checkSolution() {
   int board[N][N];
   for(int i = 0; i<N; i++)
   for(int j = 0; j<N; j++)
   board[i][j] = 0; //set all elements to 0
   if ( solveNQueen(board, 0) == false ) { //starting from 0th column
      cout << "Solution does not exist";
      return false;
   }
   printBoard(board);
   return true;
}
int main() {
   checkSolution();
}



// Graph Coloring 

#include<bits/stdc++.h>
 
using namespace std;
 
int n,e,i,j;
vector<vector<int> > graph;
vector<int> color;
bool vis[100011];
 
void greedyColoring()
{
    color[0]  = 0;
    for (i=1;i<n;i++)
        color[i] = -1;
 
    bool unused[n];
 for (i=0;i<n;i++)
        unused[i]=0;
 
 
    for (i = 1; i < n; i++)
    {
        for (j=0;j<graph[i].size();j++)
            if (color[graph[i][j]] != -1)
                unused[color[graph[i][j]]] = true;
        int cr;
        for (cr=0;cr<n;cr++)
            if (unused[cr] == false)
                break;
  color[i] = cr; 
 
        for (j=0;j<graph[i].size();j++)
            if (color[graph[i][j]] != -1)
                unused[color[graph[i][j]]] = false;
    }
}
int main()
{
    int x,y;
    cout<<"Enter number of vertices and edges respectively:";
    cin>>n>>e;
    cout<<"\n";
    graph.resize(n);
    color.resize(n);
    memset(vis,0,sizeof(vis));
    for(i=0;i<e;i++)
    {
        cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
        cin>>x>>y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
greedyColoring();
    for(i=0;i<n;i++)
    {
        cout<<"Vertex "<<i+1<<" is coloured "<<color[i]+1<<"\n";
    }
}



// Subset Sum

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

// Print all subsets if there is atleast one subset of set[]
// with sum equal to given sum
bool flag = 0;
void PrintSubsetSum(int i, int n, int set[], int targetSum,
     vector<int>& subset)
{
 // targetSum is zero then there exist a
 // subset.
 if (targetSum == 0) {

  // Prints valid subset
  flag = 1;
  cout << "[ ";
  for (int i = 0; i < subset.size(); i++) {
   cout << subset[i] << " ";
  }
  cout << "]";
  return;
 }

 if (i == n) {
  // return if we have reached at the end of the array
  return;
 }

 // Not considering current element
 PrintSubsetSum(i + 1, n, set, targetSum, subset);

 // consider current element if it is less than or equal
 // to targetSum
 if (set[i] <= targetSum) {

  // push the current element in subset
  subset.push_back(set[i]);

  // Recursive call for consider current element
  PrintSubsetSum(i + 1, n, set, targetSum - set[i],
     subset);

  // pop-back element after recursive call to restore
  // subsets original configuration
  subset.pop_back();
 }
}

// Driver code
int main()
{
 // Test case 1
 int set[] = { 1, 2, 1 };
 int sum = 3;
 int n = sizeof(set) / sizeof(set[0]);
 vector<int> subset;
 cout << "Output 1:" << endl;
 PrintSubsetSum(0, n, set, sum, subset);
 cout << endl;
 flag = 0;
 // Test case 2
 int set2[] = { 3, 34, 4, 12, 5, 2 };
 int sum2 = 30;
 int n2 = sizeof(set) / sizeof(set[0]);
 vector<int> subset2;
 cout << "Output 2:" << endl;
 PrintSubsetSum(0, n2, set2, sum2, subset2);
 if (!flag) {
  cout << "There is no such subset";
 }

 return 0;
}


// Topological sort

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

void topo_sort(int vertices, int edges) {
    vector<char> ans;
    queue<char> q;
    map<char, vector<char>> graph;
    map<char, int> inDegree;

    vector<pair<char, char>> edgeList = {{'A', 'B'},{'A', 'C'},{'B', 'D'},{'B', 'E'},{'C', 'E'},{'D', 'F'},{'E', 'F'}};

    for (int i = 0; i < edges; i++) {
        char a = edgeList[i].first;
        char b = edgeList[i].second;
        graph[a].push_back(b);
        inDegree[b]++;
    }

    for (char c = 'A'; c <= 'F'; c++) if (inDegree[c] == 0) q.push(c);

    while (!q.empty()) {
        char v = q.front();
        q.pop();
        ans.push_back(v);
        for (int i = 0; i < graph[v].size(); i++) {
            char u = graph[v][i];
            inDegree[u]--;
            if (inDegree[u] == 0) {
                q.push(u);
            }
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];
        if (i < ans.size() - 1)  cout << "->";
    }
}

int main() {
    int vertices = 6;
    int edges = 7;
    topo_sort(vertices, edges);
    return 0;
}






*/