886

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:

        g = defaultdict(list)
        visited = defaultdict(int)
        for a, b in dislikes:
            g[a].append(b)
            g[b].append(a)


        for v in g:
            if visited[v] == 0:
                st = [v]
                visited[v] = 1
                while st:
                    cur = st.pop()
                    color = 2 if visited[cur] == 1 else 1
                    for n in g[cur]:
                        if visited[n] == 0:
                            visited[n] = color
                            st.append(n)
                        elif visited[n] != color:
                            return False

        return True