"""
https://leetcode.com/problems/possible-bipartition/
"""


from typing import List
from collections import defaultdict, deque


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

        memo = defaultdict(list)  # number: dislikes list
        visited = {}  # number: color
        for k, v in dislikes:
            memo[k].append(v)
            memo[v].append(k)

        for num in memo:
            if num not in visited:
                queue = deque([(num, 1)])
                while queue:
                    curr, color = queue.popleft()
                    if curr not in visited:
                        visited[curr] = color
                        for neighbor in memo[curr]:
                            queue.append((neighbor, -color))

                    if visited[curr] != color:
                        return False

        return True

fefc23e48a88451b4ba0a5cf37f83e88bfa5c9e7
<mask token>

<mask token>


class Solution:
    <mask token>

<mask token>


class Solution:

    def possibleBipartition(self, N: int, dislikes: List[List[int]]) ->bool:
        if not dislikes:
            return True
        memo = defaultdict(list)
        visited = {}
        for k, v in dislikes:
            memo[k].append(v)
            memo[v].append(k)
        for num in memo:
            if num not in visited:
                queue = deque([(num, 1)])
                while queue:
                    curr, color = queue.popleft()
                    if curr not in visited:
                        visited[curr] = color
                        for neighbor in memo[curr]:
                            queue.append((neighbor, -color))
                    if visited[curr] != color:
                        return False
        return True

<mask token>
from typing import List
from collections import defaultdict, deque


class Solution:

    def possibleBipartition(self, N: int, dislikes: List[List[int]]) ->bool:
        if not dislikes:
            return True
        memo = defaultdict(list)
        visited = {}
        for k, v in dislikes:
            memo[k].append(v)
            memo[v].append(k)
        for num in memo:
            if num not in visited:
                queue = deque([(num, 1)])
                while queue:
                    curr, color = queue.popleft()
                    if curr not in visited:
                        visited[curr] = color
                        for neighbor in memo[curr]:
                            queue.append((neighbor, -color))
                    if visited[curr] != color:
                        return False
        return True

"""
https://leetcode.com/problems/possible-bipartition/
"""


from typing import List
from collections import defaultdict, deque


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

        memo = defaultdict(list)  # number: dislikes list
        visited = {}  # number: color
        for k, v in dislikes:
            memo[k].append(v)
            memo[v].append(k)

        for num in memo:
            if num not in visited:
                queue = deque([(num, 1)])
                while queue:
                    curr, color = queue.popleft()
                    if curr not in visited:
                        visited[curr] = color
                        for neighbor in memo[curr]:
                            queue.append((neighbor, -color))

                    if visited[curr] != color:
                        return False

        return True
