from collections import deque

    def is_bipartite(graph):

        color = {}

        for node in graph:
            if node not in color:
                queue = deque([node])
                color[node] = 0  # start coloring with 0

                while queue:
                    u = queue.popleft()
                    for v in graph[u]:
                        if v not in color:
                            color[v] = 1 - color[u]  # alternate color
                            queue.append(v)
                        elif color[v] == color[u]:
                            return False  # conflict detected

        return True

    def is_bipartite_dfs(graph):
        color = {}

        def dfs(node, c):
            color[node] = c
            for neighbor in graph[node]:
                if neighbor not in color:
                    if not dfs(neighbor, 1 - c):
                        return False
                elif color[neighbor] == c:
                    return False
            return True

        for node in graph:
            if node not in color:
                if not dfs(node, 0):
                    return False

        return True

  oh! pseudocode hasn't been written yet, try another card! :)

    def isBipartite(self, graph: List[List[int]]) -> bool:

        # Bipartite Rule:
        # A graph is bipartite if every node can be colored one of two
        # colors such that no edge ever connects two nodes of the same
        # color. If we can 2-color the whole graph without conflict,
        # it's bipartite. If we ever find an edge between two same-colored
        # nodes, it's not.

        # Two-Coloring via DFS:
        # Start each uncolored node fresh, color it, then recursively
        # color every neighbor the OPPOSITE color. If a neighbor is
        # already colored, it must already be the opposite color --
        # if it's the same color instead, that's a direct contradiction.

        # Why DFS works here:
        # We don't care about shortest paths or traversal order, only
        # that colors alternate correctly across every edge. DFS visits
        # each node once and checks all its edges, same guarantee as BFS,
        # just via recursion instead of a queue.

        # Disconnected Graphs:
        # The graph may not be fully connected, so we must attempt to
        # start a fresh coloring from every node that hasn't been
        # colored yet, not just node 0.

        n = len(graph)

        # sc: O(n), 0 = uncolored, 1 = color A, -1 = color B
        color = [0] * n

        # DFS:
        # colors the current node with the given color, then recurses
        # into every neighbor, coloring them the opposite color.
        # Returns False the moment a conflict is found.
        def dfs(node, c):

            # Assign:
            # color current node with c
            color[node] = c

            # tc: O(degree(node)), visits every edge from this node once
            for nei in graph[node]:

                # Check: neighbor is uncolored
                # Implies: this edge hasn't been checked yet
                # Then: recursively color it the opposite color,
                # propagate any conflict found deeper in the recursion
                if color[nei] == 0:
                    if not dfs(nei, -c):
                        return False

                # Check: neighbor is already colored the SAME as current
                # Implies: this edge connects two same-colored nodes
                # Then: bipartite coloring is impossible, conflict found
                elif color[nei] == c:
                    return False

            # No conflicts found from this node or anything below it
            return True

        # Components:
        # graph may be disconnected, so every uncolored node needs
        # its own fresh DFS start
        # tc: O(n), across all starts combined, each node is only
        # ever colored once, so total work stays O(n + edges)
        for i in range(n):

            # Check: node i is uncolored
            # Implies: it belongs to a component we haven't visited yet
            # Then: attempt to 2-color this whole component,
            # bail out immediately if any conflict is found
            if color[i] == 0:
                if not dfs(i, 1):
                    return False

        # Every component colored without conflict: bipartite
        return True

        # overall: tc O(n + e), n = nodes, e = total edges (sum of
        # graph[u] lengths), each node colored once, each edge checked
        # once from each endpoint
        # overall: sc O(n), for the color array + recursion stack depth

    def isBipartite(self, graph: List[List[int]]) -> bool:

        # Initialization
        n = len(graph)              # number of nodes
        color = [0] * n             # 0 = uncolored, 1 = color A, -1 = color B
        
        # Traverse all components (graph may be disconnected)
        for i in range(n):
            if color[i] != 0:
                continue            # already colored in a previous BFS
            
            # Start BFS from uncolored node i
            queue = deque([i])
            color[i] = 1             # assign initial color
            
            # BFS traversal for coloring
            while queue:
                node = queue.popleft()
                
                # Explore neighbors
                for nei in graph[node]:
                    
                    if color[nei] == 0:
                        # Neighbor uncolored: assign opposite color
                        color[nei] = -color[node]
                        queue.append(nei)
                    
                    elif color[nei] == color[node]:
                        # Neighbor already colored same as current: conflict
                        # Graph is not bipartite
                        return False
        
        # If all nodes processed without conflict: bipartite
        return True

  oh! pseudocode hasn't been written yet, try another card! :)

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:

        # Bipartite Rule:
        # Splitting people into two groups such that no two people in
        # the same group dislike each other is exactly the bipartite
        # coloring problem: build an edge between every disliking pair,
        # then check whether the resulting graph can be 2-colored with
        # no edge connecting two same-colored nodes.

        # Build Graph:
        # Each dislike pair is an undirected edge -- if a dislikes b,
        # b also can't be grouped with a, so the edge goes both ways.

        # sc: O(n + d), d = len(dislikes), adjacency list of all people
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        # Two-Coloring via DFS:
        # Start each uncolored person fresh, color them, then recursively
        # color every person they dislike the OPPOSITE color/group. If
        # someone is already colored, they must already be the opposite
        # color -- if it's the same color instead, that's a direct
        # contradiction (two people who dislike each other, same group).

        # Why DFS works here:
        # We don't care about traversal order, only that colors alternate
        # correctly across every disliking edge. DFS visits each person
        # once and checks all their disliking edges, same guarantee as
        # BFS, just via recursion instead of a queue.

        # Disconnected Graphs:
        # Not everyone is guaranteed to dislike (or be disliked by)
        # someone else, and the dislike graph as a whole may be split
        # into several separate components, so every uncolored person
        # needs their own fresh DFS start.

        # sc: O(n), 0 = uncolored, 1 = group A, -1 = group B
        color = [0] * (n + 1)

        # DFS:
        # colors the current person with the given color, then recurses
        # into every person they dislike, coloring them the opposite
        # color. Returns False the moment a conflict is found.
        def dfs(person, c):

            # Assign:
            # color current person with c
            color[person] = c

            # tc: O(degree(person)), visits every disliking edge once
            for nei in graph[person]:

                # Check: neighbor is uncolored
                # Implies: this disliking edge hasn't been checked yet
                # Then: recursively color it the opposite group,
                # propagate any conflict found deeper in the recursion
                if color[nei] == 0:
                    if not dfs(nei, -c):
                        return False

                # Check: neighbor is already colored the SAME as current
                # Implies: two people who dislike each other are stuck
                # in the same group
                # Then: bipartition is impossible, conflict found
                elif color[nei] == c:
                    return False

            # No conflicts found from this person or anything below them
            return True

        # Components:
        # dislike graph may be disconnected, so every uncolored person
        # needs their own fresh DFS start
        # tc: O(n), across all starts combined, each person is only
        # ever colored once, so total work stays O(n + d)
        for person in range(1, n + 1):

            # Check: person is uncolored
            # Implies: they belong to a component we haven't visited yet
            # Then: attempt to 2-color this whole component,
            # bail out immediately if any conflict is found
            if color[person] == 0:
                if not dfs(person, 1):
                    return False

        # Every component colored without conflict: valid bipartition
        return True

        # overall: tc O(n + d), n = people, d = len(dislikes), each
        # person colored once, each disliking edge checked once from
        # each endpoint
        # overall: sc O(n + d), graph adjacency list + color array +
        # recursion stack depth

    def possibleBipartition(self, n, dislikes):
        # Build graph
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        # 0 = uncolored, 1 / -1 = two groups
        color = [0] * (n + 1)

        # Handle disconnected components
        for person in range(1, n + 1):
            if color[person] != 0:
                continue

            queue = deque([person])
            color[person] = 1

            while queue:
                cur = queue.popleft()

                for nei in graph[cur]:
                    # conflict → same color
                    if color[nei] == color[cur]:
                        return False

                    if color[nei] == 0:
                        color[nei] = -color[cur]
                        queue.append(nei)

        return True