1
# Runtime: 997 ms (Top 62.25%) | Memory: 22.2 MB (Top 22.99%)
2
class Solution:
3
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
4
        def dfs(i, c):
5
            if color[i] != 0:
6
                if color[i] != c:
7
                    return False
8
                return True
9

10
            color[i] = c
11
            for u in e[i]:
12
                if not dfs(u, 3 - c):
13
                    return False
14
            return True
15

16
        e = [[] for _ in range(n)]
17
        for u, v in dislikes:
18
            u -= 1
19
            v -= 1
20
            e[u].append(v)
21
            e[v].append(u)
22
        color = [0] * n
23
        for i in range(n):
24
            if color[i] == 0:
25
                if not dfs(i, 1):
26
                    return False
27
        return True