class Solution {
    public boolean isBipartite(int V, int[][] edges) {

        // create a adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Integer>());
        }
        
        // fill the adjacency list
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            
            // undirected graph
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        for(int i=0; i<V; i++)
        {
            // only start BFS if node is uncolored
            if (color[i] == -1) 
            {  
                if(bfs(adj, color, i) == false)
                    return false;
            }
        }
        return true;
    }
    
    public boolean bfs(ArrayList<ArrayList<Integer>> adj, int[] color, int node)
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        color[node] = 0;
        
        while(!q.isEmpty())
        {
            int u = q.poll();
            
            for(int v : adj.get(u))
            {
                // neighbour node and current node has same color, so not a bipartite graph
                if(color[v] == color[u])
                    return false;
                    
                // assign opposite color
                else if(color[v] == -1)
                {
                    // assigning opposite color
                    color[v] = 1 - color[u];
                    q.add(v);
                }
            }
        }
        return true;
    }
}