bipartite graph

// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
/*
algorithm:bfs
method: check whether vertex coloring==2?
-1------------------------->not visited
0 -------------------------> color 1
1-------------------------->color 2
*/



class Solution {
public:
bool bfs(vector<int> adj[],int colors[],int src){
        queue<int> q;
        q.push(src);
        colors[src]=0;
        while(!q.empty()){
            int t=q.front();
            q.pop();
            for(auto i:adj[t])
                if (i==t)
                    return false;
                else if (colors[i]==-1 ){
                colors[i]=1-colors[t];
                q.push(i);
                       }
                else if (colors[i]==colors[t])
                return false;
                }
        return true;

}
    bool isBipartite(int V, vector<int>adj[]){
        // Code here
        int colors[V];
       // memset(colors,-1,sizeof(colors));
       for(int i=0;i<V;++i)
        colors[i]=-1;
        for(int i=0;i<V;++i)
        if (colors[i]==-1 && !bfs(adj,colors,i))
            return false;
       return true;


    }

};

// { Driver Code Starts.
int main(){
    int tc;
    cin >> tc;
    while(tc--){
        int V, E;
        cin >> V >> E;
        vector<int>adj[V];
        for(int i = 0; i < E; i++){
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        Solution obj;
        bool ans = obj.isBipartite(V, adj);
        if(ans)cout << "1\n";
        else cout << "0\n";
    }
    return 0;
}  // } Driver Code Ends