Программа отлично работает только для одного теста — отладка

Я хочу знать, является ли мой график двудольным или нет, у меня есть несколько тестовых случаев. Если я запускаю более одного тестового примера, он не работает должным образом, он всегда показывает Bipartite. Мне трудно понять это. Только для одного случая он отлично работает для любого графика.
Здесь идет мой код.

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