class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color=new int[graph.length];
        Arrays.fill(color,-1);
        boolean isBipartite=true;
        for(int i=0;i<graph.length;i++)
        {
            if(color[i]==-1)
            {
                isBipartite=isBipartite && isbipartite(graph,i,color);
                if(isBipartite==false)return false;
            }
        }
        
        return true;
    }
    public boolean isbipartite(int g[][], int n, int color[])
    {
        Queue<Integer> q= new LinkedList<Integer>();
        color[n]=0;
        q.add(n);
        while(!q.isEmpty())
        {
            int top=q.remove();
            for(int i=0;i<g[top].length;i++)
            {
                int adj=g[top][i];
                if(color[adj]==-1)
                {
                    color[adj]=1-color[top];
                    q.add(adj);
                }
                else if(color[adj]==color[top])
                    return false;
            }
        }
        return true;
    }
   
}

class Solution {
    public boolean graphColor(int [][] graph, int curr, int []color){
        if(color[curr]==-1)
            color[curr]=1;
        for(int adj : graph[curr]){
            if(color[adj]==-1){
                color[adj]=1-color[curr];
                if(graphColor(graph,adj,color)==false)
                    return false;
            }
                else if(color[adj]==color[curr])
                    return false;
            }
        
        return true;
    }
    public boolean isBipartite(int[][] graph) {
       int color[] =new int[graph.length];
        Arrays.fill(color,-1);
        boolean isBipartite=true;
        for(int i=0;i<graph.length;i++){
            if(color[i]==-1)
            {
                isBipartite=graphColor(graph,i,color);
                    if(isBipartite==false)
                        return false;
            }
        }
        return true;
    }
}