**PLEASE USE C++**

3. (5 points) Write a program to check whether a given graph is bipartite or not. For this, Step 1. In the main function, read the input from a file "input-graph.txt" which has the following format 6 0 1 1 0 0 0 100 0 0 0 100 0 0 0 00 00 1 1 000 1 0 1 0 0 0 1 1 0 The first line denote the number of nodes n in the input graph G, and then the n2 binary values specify the adjacency matrix of G. Assume that the nodes of G are numbered from 0,. ,n-1. The first row of adjacency matrix represents the adjacency of node 0 where the value 1 in the jthcolumn indicates that there is an edge between nodes 0 and j and the value 0 in the jth column indicates that there is no edge between nodes 0 and The second row represents the adjacency of node 1, and so on. Read the first number in a variable n, and then create a two-dimensional array G of size n n, and then read the adjacency matrix in G Step 2. Implement the following function prototype bool isBipartite(int **G, int n) which takes an undirected graph G and the num- ber of nodes n in G as its input, and outputs whether G is a bipartite graph or not. Make sure to handle the situation when G is not connected. A graph G is said to be connected if there is a path between every pair of vertices. Observe that the graph in the above input is not connected Step 3. Call isBipartite in the main function with the input read in Step 1, and print the message based on the return value. For example, your answer in case of the above input instance should be: Graph is not bipartite. (HINT: Modify the BFS algorithm implemented i lab7. Recall that an undirected graph G is bipartite if and only if there are no odd cycles in G. Further, odd cycle in a graph can be detected using BFS by checking if there is an edge between two nodes at the same level)