Write a C++ program to solve the Knapsack problem

using Branch and Bound.

Write a Program to check whether a given

graph is connected or not using DFS
method.

PRACTICAL - 1

Write a C++ program to perform QuickSort using Divide and Conquer

Technique
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[],int low,int high)
{
//choose the pivot

int pivot=arr[high];
//Index of smaller element and Indicate
//the right position of pivot found so far
int i=(low-1);

for(int j=low;j<=high;j++)
{
//If current element is smaller than the pivot
if(arr[j]<pivot)
{
//Increment index of smaller element
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1],arr[high]);
return (i+1);
}

// The Quicksort function Implement

void quickSort(int arr[],int low,int high)

{
// when low is less than high
if(low<high)
{
// pi is the partition return index of pivot

int pi=partition(arr,low,high);

//Recursion Call
//smaller element than pivot goes left and
//higher element goes right quickSort(arr,low,pi-
1);
quickSort(arr,pi+1,high);
}
}

int main() { int

arr[]={10,7,8,9,1,5};
int n=sizeof(arr)/sizeof(arr[0]);

// Function call
quickSort(arr,0,n-1);
//Print the sorted array
cout<<"Sorted Array\n";
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
 PRACTICAL - 2

Write a C++ program to perform MergeSort using Divide and Conquer

Technique
// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of array[].
// First subarray is arr[begin..mid] //
Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
int const right)
{ int const subArrayOne = mid - left +
1; int const subArrayTwo = right -
mid;

// Create temp arrays

auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temp arrays leftArray[] and rightArray[]

for (auto i = 0; i < subArrayOne; i++) leftArray[i] =
array[left + i]; for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;

int indexOfMergedArray = left;

// Merge the temp arrays back into array[left..right]

while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) { if
(leftArray[indexOfSubArrayOne] <=
rightArray[indexOfSubArrayTwo])
{ array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}

// Copy the remaining elements of

// left[], if there are any
while (indexOfSubArrayOne < subArrayOne)
{ array[indexOfMergedArray] =
leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}

// Copy the remaining elements of

// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray] =
rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
 } delete[]
leftArray; delete[]
rightArray;
}

// begin is for left index and end is right

index // of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{ if (begin >=
end)
return;

int mid = begin + (end - begin) / 2;

mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
// Function to print an array
vprintArray(int A[], int
{
for (int i = 0; i < size; i++)
cout << A[i] << " "; cout
<< endl;
}

// Driver
code int
main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \

n"; printArray(arr, arr_size);
return 0;
}

OUTPUT
 PRACTICAL - 3
Write a C++ program to find all the ShortestPath using FloydWarshall
Algorithm
#include <iostream> using
namespace std;
#define INF 1000000000 // Infinity

void printPath(int parent[], int i, int j)

{ if (i == j) cout << i << " ";
else if (parent[j] == -1) cout <<
"No path exists"; else {
printPath(parent, i, parent[j]);
cout << j << " ";
}
}

int main()
{
int V = 4;
// V represent number of vertices
int dist[V][V] = {{0, 2, INF, 4},
{6, 0, 5, 3},
{INF, 10, 0, 1},
{7, 9, 8, 0}};
// Represent the graph using adjacency matrix

// Apply the Floyd Warshall algorithm to find the shortest paths

int parent[V][V]; for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] != INF && i != j)
parent[i][j] = i;
else
parent[i][j] = -1;
}
}
// update the path and distance using the k vertex range from 0 to V-1.
for (int k = 0; k < V; k++)
{for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
parent[i][j] = parent[k][j];
}
}
}
 }
// Print shortest distances and paths between all pairs of vertices
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cout << "The Shortest distance between " << i << " and " << j << " is
"; if (dist[i][j] == INF) cout << "INF ";
else
cout << dist[i][j] << " ";

cout << "and the shortest path is:- ";

printPath(parent[i], i, j);
cout << endl;
}
}

return
0; }

OUTPUT

PRACTICAL - 4

Write a C++ program to solve a Knapsack problem using Greedy

Approach
 // C++ program to solve fractional
// Knapsack Problem
#include <bits/stdc++.h>

using namespace std;

// Structure for an item which stores //

weight & corresponding value of Item
struct Item {
int value, weight;

// Constructor
Item(int value, int weight)
: value(value), weight(weight)
{
}
};

// Comparison function to sort

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

// Main greedy function to solve problem

double fractionalKnapsack(struct Item arr[],
int N, int size)
{
// Sort Item on basis of ratio
sort(arr, arr + size, cmp);

// Current weight in knapsack

int curWeight = 0;

// Result (value in Knapsack)

double finalvalue = 0.0;

// Looping through all Items

for (int i = 0; i < size; i++) {

// If adding Item won't overflow,

// add it completely if
(curWeight + arr[i].weight <= N) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}

// If we can't add current Item,

// add fractional part of it
else {
int remain = N -
curWeight; finalvalue +=
arr[i].value *
((double)remain
/ arr[i].weight);
 break;
}
}

// Returning final value

return finalvalue;
}

// Driver Code
int main()
{
// Weight of knapsack
int N = 60;

// Given weights and values as a pairs

Item arr[] = { { 100, 10 },
{ 280, 40 },
{ 120, 20 },
{ 120, 24 } };

int size = sizeof(arr) / sizeof(arr[0]);

// Function Call
cout << "Maximum profit earned = "
<< fractionalKnapsack(arr, N, size);
return 0;
}

OUTPUT

PRACTICAL - 5

Write a C++ program for Shortest Path using Dijkstra’s Algorithm

// A C++ program for Dijkstra's single source shortest path
// algorithm. The program is for adjacency matrix
// representation of the graph

#include <limits.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 9
// A utility function to find the vertex with minimum
// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance

// array
void printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("\t%d \t\t\t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source

// shortest path algorithm for a graph represented using
// adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the
// shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is

// included in shortest
// path tree or shortest distance from src to i is
// finalized

// Initialize all distances as INFINITE and stpSet[] as

// false

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices for (int count

= 0; count < V - 1; count++) { // Pick the
minimum distance vertex from the set of // vertices
not yet processed. u is always equal to // src in the
first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the

// picked vertex.
 for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet,

// there is an edge from u to v, and total
// weight of path from src to v through u
is // smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] &&
dist[u] != INT_MAX && dist[u] +
graph[u][v] < dist[v]) dist[v] = dist[u] +
graph[u][v];
}

// print the constructed distance array

printSolution(dist, V);
}

// driver program to test above function

int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}

OUTPUT
 PRACTICAL - 6
Write a C++ program to find Minimum Spanning Tree using Prim’s
Algorithm.
// A C++ program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph

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

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

// A utility function to print the // constructed

MST stored in parent[] void printMST(int
parent[], int graph[V][V])
{
cout << "Edge \tWeight\n"; for (int i
= 1; i < V; i++) cout << parent[i] << "
- " << i << " \t"
<< graph[i][parent[i]] << " \n";
}

// Function to construct and print MST for

// a graph represented using adjacency
// matrix representation void
primMST(int graph[V][V])
{
// Array to store constructed MST
int parent[V];

// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices included in MST

bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
 // Always include first 1st vertex in MST. //
Make key 0 so that this vertex is picked as
first // vertex. key[0] = 0;

// First node is always root of MST

parent[0] = -1;

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum key vertex from the

// set of vertices not yet included in MST
int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent

// vertices of m mstSet[v] is false for vertices
// not yet included in MST Update the key
only // if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false &&
graph[u][v] < key[v]) parent[v] = u, key[v]
= graph[u][v];
}

// Print the constructed MST

printMST(parent, graph);
}

// Driver's
code int
main() {
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;
}
OUTPUT
 PRACTICAL - 7

Write a C++ program for Sum of Subsets Problem using Backtracking.

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

OUTPUT

PRACTICAL – 8
Write a C++ program to solve TravellingSales problem using the Dynamic
Programming Approach.
#include <iostream>

using namespace std;

// there are four nodes in example graph (graph is 1-based)

const int n = 4;
// give appropriate maximum to avoid overflow
const int MAX = 1000000;
// dist[i][j] represents shortest distance to go from i to j
// this matrix can be calculated for any given graph using
// all-pair shortest path algorithms
int dist[n + 1][n + 1] = {
{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};

// memoization for top down recursion

int memo[n + 1][1 << (n + 1)];

int fun(int i, int mask)

{
// base case
// if only ith bit and 1st bit is set in our mask, //
it implies we have visited all other nodes already
if (mask == ((1 << i) | 3)) return dist[1][i]; //
memoization if (memo[i][mask] != 0) return
memo[i][mask];

int res = MAX; // result of this sub-problem //

we have to travel all nodes j in mask and end the
// path at ith node so for every node j in mask,
// recursively calculate cost of travelling all nodes in
// mask except i and then travel back from node j to
// node i taking the shortest path take the minimum of
// all possible j nodes

for (int j = 1; j <= n; j++)

if ((mask & (1 << j)) && j != i && j != 1)
res = std::min(res, fun(j, mask & (~(1 << i)))
+ dist[j][i]);
return memo[i][mask] = res;
}

// Driver program to test above logic

int main()
{
int ans = MAX;
for (int i = 1; i <= n; i++)
// try to go from node 1 visiting all nodes in
// between to i then return from i taking the
// shortest route to 1
ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)
+ dist[i][1]);

printf("The cost of most efficient tour = %d", ans);

return 0;
}
 OUTPUT

PRACTICAL – 9

Write a C++ program to find solution of N Queen Problem using

Backtracking.

// C++ program to solve N Queen Problem using backtracking

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

// A utility function to print solution void

printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if(board[i][j])
cout << "Q "; else
cout<<". ";
printf("\n");
}
}

// A utility function to check if a queen can

// be placed on board[row][col]. Note that this
// function is called when "col" queens are //
already placed in columns from 0 to col -1.
// So we need to check only left side for
// attacking queens
bool isSafe(int board[N][N], int row, int col)
{
int i, j;

// Check this row on left side

for (i = 0; i < col; i++) if
(board[row][i]) return
false;

// Check upper diagonal on left side for (i =

row, j = col; i >= 0 && j >= 0; i--, j--) if
(board[i][j])
return false;
 // Check lower diagonal on left side for (i =
row, j = col; j >= 0 && i < N; i++, j--) if
(board[i][j])
return false;

return true;
}

// A recursive utility function to solve N

// Queen problem
bool solveNQUtil(int board[N][N], int col)
{
// base case: If all queens are placed
// then return true
if (col >= N)
return true;
// Consider this column and try placing
// this queen in all rows one by one for
(int i = 0; i < N; i++) {

// Check if the queen can be placed on

// board[i][col]
if (isSafe(board, i, col)) {

// Place this queen in board[i][col]

board[i][col] = 1;

// recur to place rest of the queens

if (solveNQUtil(board, col + 1))
return true;

// If placing queen in board[i][col]

// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] = 0; // BACKTRACK
}
}

// If the queen cannot be placed in any row

in // this column col then return false
return false;
}

// This function solves the N Queen problem using

// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if
queens // cannot be placed, otherwise, return
true and // prints placement of queens in the
form of 1s.
// Please note that there may be more than
one // solutions, this function prints one of
the // feasible solutions. bool solveNQ() {
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist";
return false;
 }

printSolution(board);
return true;
}

// Driver program to test above

function int main() { solveNQ();
return 0;
}

OUTPUT

PRACTICAL – 10

Write a C++ program to solve the Knapsack Problem using Branch & Bound.

// 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 --> Level of node in decision tree (or index
// in arr[]
// profit --> Profit of nodes on path from root to this
// node (including this node)
 // bound ---> 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;
}

// Returns bound of profit in subtree rooted with

u. // This function mainly uses Greedy solution to
find // an upper bound on maximum profit.
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 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; }

OUTPUT
 PRACTICAL – 11

Write a program to Check whether a given graph is connected or not using

DFS method.

// C++ implementation of the approach

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

// To keep correct and reverse direction vector<int>

gr1[N], gr2[N];

bool vis1[N], vis2[N];

// Function to add edges

void Add_edge(int u, int v)
{
gr1[u].push_back(v);
gr2[v].push_back(u);
}

// DFS function
void dfs1(int x)
{
vis1[x] = true;

for (auto i :
gr1[x]) if (!
vis1[i])
dfs1(i);
}

// DFS function
void dfs2(int x)
{
vis2[x] = true;

for (auto i :
gr2[x]) if (!
vis2[i])
dfs2(i);
}

bool Is_Connected(int n)
{
// Call for correct direction
memset(vis1, false, sizeof vis1);
dfs1(1);
// Call for reverse direction
memset(vis2, false, sizeof vis2);
dfs2(1);

for (int i = 1; i <= n; i++) {

// If any vertex it not visited in any direction

 // Then graph is not connected
if (!vis1[i] and !vis2[i])
return false;
}

// If graph is connected
return true;
}

// Driver
code int
main() {
int n = 4;

// Add edges
Add_edge(1, 2);
Add_edge(1, 3);
Add_edge(2, 3);
Add_edge(3, 4);

// Function call if
(Is_Connected(n))
cout << "Yes"; else
cout << "No";

return 0;
}

OUTPUT