I want to know whether my graph is bipartite or not, I have several test cases. If I run more than one test case it doesn't work properly, it always shows Bipartite. I am having a hard time figuring it out. For just one case, it works fine for any graph.

Here goes my code.

```
#include <iostream>
#include <cstdio>
#include <stack>
#include <list>
using namespace std;
class Graph
{
public:
int V;
list<int> *adj;
Graph(int V);
void addEdge(int v, int w);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
class Bipartite
{
private:
bool isBipartite;
bool *color;
bool *marked;
int *edgeTo;
stack<int> cycle;
public:
Bipartite(Graph G)
{
isBipartite = true;
color = new bool [G.V];
marked = new bool [G.V];
edgeTo = new int [G.V];
for (int v = 0; v < G.V; v++)
{
if (!marked[v])
{
color[v] = false;
dfs(G, v);
}
}
delete color;
delete marked;
delete edgeTo;
}
void dfs(Graph G, int v)
{
marked[v] = true;
list<int>::iterator w;
for (w = G.adj[v].begin(); w != G.adj[v].end(); w++)
{
if (!cycle.empty())
return;
if (!marked[*w])
{
edgeTo[*w] = v;
color[*w] = !color[v];
dfs(G, *w);
}
else if (color[*w] == color[v])
{
isBipartite = false;
cycle.push(*w);
for (int x = v; x != *w; x = edgeTo[x])
{
cycle.push(x);
}
cycle.push(*w);
}
}
}
bool isBi()
{
return isBipartite;
}
};
void solve(int n,int **p){
long long int x,y;
Graph g(n);
for(x=0;x<n;x++)
for(y=0;y<n;y++)
{
if(p[x][y]==1)
g.addEdge(x,y);
}
Bipartite b(g);
if (b.isBi())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
int main()
{
long long int i,j,t,x,m,y,a,b;
int **p,n;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n>>m;
p=new int*[n]();
for(x=0;x<n;x++)
{
p[x]=new int[n]();
}
for(j=0;j<m;j++)
{
cin>>a>>b;
a=a-1;
b=b-1;
p[a][b]=1;
p[b][a]=1;
}
for(x=0;x<n;x++)
{
for(y=0;y<n;y++)
{
if(x!=y)
{
p[x][y]=1-p[x][y];
}
}
}
/* for(x=0;x<n;x++)
{
for(y=0;y<n;y++)
cout<<p[x][y]<<" ";
cout<<"\n";
}
*/
solve(n,p);
}
return 0;
}
```