Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group. 
Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.
Return true if and only if it is possible to split everyone into two groups in this way.
 







Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]


Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false


Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false




 
Constraints:

1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        group = [None] * (N + 1)
        group[dislikes[0][0]] = 1
        group[dislikes[0][1]] = -1
        group1 = set([1])
        group2 = set()
        counter = 2
        for i, j in dislikes[1:]:
            if group[i] and group[j]:
                if group[i] == group[j]:
                    return False
                if group[i] in group1:
                    if group[j] in group1 or -group[j] in group2:
                        return False
                    group2.add(group[j])
                elif group[i] in group2:
                    if group[j] in group2 or -group[j] in group1:
                        return False
                    group1.add(group[j])
                elif group[j] in group1:
                    if group[i] in group1 or -group[i] in group2:
                        return False
                    group2.add(group[i])
                elif group[j] in group2:
                    if group[i] in group2 or -group[i] in group1:
                        return False
                    group1.add(group[i])
            elif not group[i] and not group[j]:
                group[i], group[j] = counter, -counter
                counter += 1
            elif group[i]:
                group[j] = -group[i]
            elif group[j]:
                group[i] = -group[j]
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        edge = [[] for _ in range(N + 1)]
        for u, v in dislikes:
            edge[u].append(v)
            edge[v].append(u)
        color = [0] * (N + 1)
        for i in range(1, N + 1):
            if color[i] == 0:
                q = [i]
                color[i] = 1
                while q:
                    cur = q.pop()
                    cur_c = color[cur]
                    for node in edge[cur]:
                        if color[node] == 0:
                            color[node] = cur_c * -1
                            q.append(node)
                        elif color[node] == cur_c:
                            return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for i, j in dislikes:
            graph[i].append(j)
            graph[j].append(i)
        
        color = dict()
        
        for i in range(1,N+1):
            if i not in color:
                if not self.dfs(i, color, graph, c=0):
                    return False
        # print(color)        
        return True        
    
    def dfs(self, idx, color, graph, c):
        # print((idx,c))
        color[idx] = c
        newc = 0 if c == 1 else 1
        for i in graph[idx]:
            if i not in color:
                if not self.dfs(i, color, graph, newc):
                    return False
            else:
                if color[i] == color[idx]:
                    return False
        return True   


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        color = {}
        for i in range(1,N+1):
            if i not in color:
                ret = self.dfs(graph,i,color,'R')
                if not ret:
                    return False
        return True
    
    def dfs(self,graph,i,color,currentColor) -> bool:
        color[i] = currentColor
        complementaryColor = 'R' if currentColor=='B' else 'B'
        for neighbor in graph[i]:
            if neighbor in color:
                if color[neighbor]==currentColor:
                    return False
            else:
                res = self.dfs(graph,neighbor,color,complementaryColor)
                if not res:
                    return False
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        groups = [0] * (N+1)
        adj = collections.defaultdict(list)
        for [i, j] in dislikes:
            adj[i].append(j)
            adj[j].append(i)
        
        def dfs(i):
            for nei in adj[i]:
                if groups[nei]:
                    if groups[nei] == groups[i]:
                        return False
                else:
                    groups[nei] = -groups[i]
                    if not dfs(nei):
                        return False
            return True
        
        for i in range(N):
            if not groups[i]:
                groups[i] = 1
                if not dfs(i):
                    return False
        return True
                


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N==1 or not dislikes:
            return True
        x={i:[] for i in range(1,N+1)}
        for i,j in dislikes:
            x[i].append(j)
            x[j].append(i)
        colour=[-1]*N
        for i in range(1,N+1):
            if colour[i-1]==-1:
                colour[i-1]=0
                q=[i]
                while q:
                    node=q.pop()
                    for j in x[node]:
                        if colour[node-1]==colour[j-1]:
                            return False
                        if colour[j-1]==-1:
                            colour[j-1]=colour[node-1]^1
                            q.append(j)
        return True


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, seen) == False:
                    return False
        return True

    def check(self, connections, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = connections[pop]
            for v in vertices:
                q.append((v, -color))
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        self.ans = True    
    
        def dfs(p, d, ld, l):
            if not self.ans:
                return

            if not p in ld:
                ld[p] = l
            else:
                if ld[p] != l:
                    self.ans = False
                return
                        
            for n in d[p]:
                dfs(n, d, ld, (l + 1) % 2)
        
        i = 0
        d = {}
        while i < len(dislikes):
            [a, b] = dislikes[i]
            if a in d:
                d[a].append(b)
            else:
                d[a] = [b]
            if b in d:
                d[b].append(a)
            else:
                d[b] = [a]
            i += 1
                
        
        ld = {}
        for k in d:
            if not k in ld:
                dfs(k, d, ld, 0)
                if not self.ans: 
                    break
                    
        return self.ans


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)

        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        people = list(graph.keys())
        belongs = [None] * (N+1)
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * (N+1)
        queue = collections.deque()

        for u in people:
            if color[u] == WHITE:
                color[u] = GRAY
                queue.append(u)
                belongs[u] = 1

                while queue:
                    v = queue.popleft()

                    for w in graph[v]:
                        if color[w] == WHITE:
                            color[w] = GRAY
                            queue.append(w)
                            belongs[w] = belongs[v] * -1
                        elif belongs[w] == belongs[v]:
                            return False

                    color[v] = BLACK

        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N == 0:
            return False
        
        dlikelist = [[] for i in range(N)]
        for p in dislikes:
            dlikelist[p[0]-1].append(p[1]-1)
            dlikelist[p[1]-1].append(p[0]-1) #Dislike is mutual
            
        seen = [-1] * N
        group = [-1] * N
        parent = [-1] * N
        
        def dfs(src):
            seen[src] = 1
            if parent[src] == -1:
                group[src] = 0
            else:
                group[src] = 1 -group[parent[src]]
            
            for p in dlikelist[src]:
                if seen[p] == -1:
                    parent[p] = src
                    if dfs(p) == False:
                        return   False
                else:
                    if group[p] == group[src]:
                        return False
            return True
            

        for i in range(N):
            if seen[i] == -1:
                if dfs(i) == False:
                    return False
        return True
        
        
        


def dfs(adjList, teams, node):
    teams[node] = 1
    stack = [node]
    while stack:
        node = stack.pop()
        team = teams[node]
        for adjNode in adjList[node]:
            if adjNode in teams and teams[adjNode] == team:
                return False
            if adjNode not in teams:
                teams[adjNode] = 1 - team
                stack.append(adjNode)
    return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        adjList = {i: [] for i in range(1, N + 1)}
        for dislike in dislikes:
            x = dislike[0]
            y = dislike[1]
            adjList[x].append(y)
            adjList[y].append(x)
            
        teams = {}
        for i in range(1, N + 1):
            if i not in teams:
                if not dfs(adjList, teams, i):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        g = [[] for _ in range(N)]
        for p in dislikes:
            p[0] -= 1
            p[1] -= 1
            g[p[0]].append(p[1])
            g[p[1]].append(p[0])
            
        col = [0] * N
        def dfs(v, c):
            col[v] = c
            for to in g[v]:
                if col[to] == c:
                    return False
                elif col[to] == 0 and not dfs(to, 3 - c):
                    return False
            return True
        for i in range(N):
            if col[i] == 0 and not dfs(i, 1):
                return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        pairs = {}
        for a,b in dislikes:
            if not a in pairs:
                pairs[a] = set()
            if not b in pairs:
                pairs[b] = set()
            pairs[a].add(b)
            pairs[b].add(a)
        seen = set()
        for i in range(1,N+1):
            if i in seen:
                continue
            curr = set([i])
            A, B = set(), set()
            A.add(i)
            flag = 1
            while len(curr):
                _next = set()
                for c in curr:
                    if c not in pairs:
                        continue
                    for n in pairs[c]:
                        if flag == 1 and n in A:
                            return False
                        if flag == 0 and n in B:
                            return False
                        if n in seen:
                            continue
                        if flag:
                            B.add(n)
                        else:
                            A.add(n)
                        seen.add(n)
                        _next.add(n)
                curr = _next
                flag ^= 1
        return True
                
                


import collections
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(curr, curr_color):
            color[curr] = curr_color
            for next in graph[curr]:
                if color[next] == None:
                    dfs(next, not curr_color)
                elif color[next] == curr_color:
                    return False
            return True
        
        graph = collections.defaultdict(list)
        color = [None] * (N + 1)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        for n in range(1, N + 1):
            if color[n] == None:
                if not dfs(n, True):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:        
        # build graph
        graph = [set() for _ in range(N+1)]
        for a,b in dislikes: 
            graph[a-1].add(b-1)
            graph[b-1].add(a-1)
        
        colors = [0] * N
        q = []
        for i in range(N):
            if colors[i] != 0: continue
            q.append(i)
            colors[i] = 1
            while q:
                cur = q.pop()
                for nxt in graph[cur]:
                    if colors[nxt] == colors[cur]: return False
                    if colors[nxt] == 0:
                        colors[nxt] = -colors[cur]
                        q.append(nxt)
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        coloring = {i:-1 for i in range(1, N+1)}
        edges = defaultdict(list)
        for a,b in dislikes:
            edges[a].append(b)
            edges[b].append(a)
        def dfs(node, color):
            if coloring[node] != -1:
                return coloring[node] == color
            coloring[node] = color
            for hater in edges[node]:
                if not dfs(hater, 1-color): return False
            return True
        return all([coloring[node]!=-1 or dfs(node, 0) for node in range(1, N+1)])


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        group = [None] * (N + 1)
        group[dislikes[0][0]] = 1
        group[dislikes[0][1]] = -1
        counter = 2
        for i, j in dislikes[1:]:
            if group[i] and group[j]:
                if group[i] == group[j]:
                    return False
                if group[i] * group[j] > 0:
                    l = group[j]
                    for k in range(N + 1):
                        if group[k] == l:
                            group[k] = -group[i]
                        if group[k] == -l:
                            group[k] = group[i]
            if not group[i] and not group[j]:
                group[i], group[j] = counter, -counter
                counter += 1
                continue
            if group[i]:
                group[j] = -group[i]
            if group[j]:
                group[i] = -group[j]
        return True

from collections import defaultdict, deque

class Solution:
    # Time: O(E) | Space: O(V+E)
    def create_adjacency_list(self, dislikes):
        adjacency_list = defaultdict(list)
        # undirected graph (a dislikes b -> b also dislikes a)
        for i , j in dislikes:
            adjacency_list[i].append(j) # since vertices numbered from 1 to N
            adjacency_list[j].append(i) # imp for undirected graph
        return adjacency_list
    
    # BFS solution
    # Time: O(V+E) | Space: O(V+E)
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # create adjacency list
        adjacency_list = self.create_adjacency_list(dislikes)
        
        print(adjacency_list)
        
        # initialize colors ( for bipartite segregation, alos serves as visited flag)
        color = {vertex:-1 for vertex in adjacency_list}
        print(color)
        
        # initialize bfs queue
        queue = deque()
        
        # call bfs on every connected component
        for vertex in adjacency_list: # remember - adjacency_list is a dict
            if color[vertex] == -1:
                # bfs
                # color the source (visited) add it to queue 
                color[vertex] = 0
                queue.append(vertex)
                
                # main bfs loop
                while queue:
                    current_node = queue.popleft()
                    for neighbor in adjacency_list[current_node]:
                        if color[neighbor] == color[current_node]:
                            return False
                        if color[neighbor] == -1:
                            # not colored (visited)
                            # color of neighbor should be opposite of current node for it to be bipartite
                            # color the neighbor and add it to queue
                            color[neighbor] = 1-color[current_node]
                            queue.append(neighbor)
            
        # if we reach here we have a valid bipartite graph
        return True
                            
                    
        
        


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N, dislikes):
        #graph = [[] * (N+1)]
        graph = [[] for _ in range(N+1)]
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        color = dict()
        def dfs(node):
            for nei in graph[node]:
                if nei in color:
                    if color[nei] == color[node]:
                        return False
                else:
                    color[nei] = color[node] ^ 1
                    if not dfs(nei):
                        return False
            return True
        for node in range(1, N+1):
            if node not in color:
                color[node] = 0
                if not dfs(node):
                    return False
        return True

from collections import defaultdict

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(node, group, groups):
            if node not in groups:
                groups[node] = group
            elif group != groups[node]:
                return True
            elif group == groups[node]:
                return False

            for next_node in graph[node]:
                fail = dfs(next_node, not groups[node], groups)
                if fail == True:
                    return True

            return False
    
        graph = defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
            
        groups = {}
        
        for node in graph:
            if node not in groups:
                fail = dfs(node, True, groups)
                if fail:
                    return False
        
        return True
                    


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        gr = [[] for _ in range(N+1)]
        A = set()
        B = set()
        
        for x in dislikes:
            gr[x[0]].append(x[1])
            gr[x[1]].append(x[0])

        done = set()
        qu = []
        
        for v in range(1, N):
            if v not in done:
                qu.append(v)
                A.add(v)
                
            while qu:
                y = qu.pop(0)
                if y not in done:
                    if y in A:
                        for x1 in gr[y]:
                            B.add(x1)
                            qu.append(x1)
                    else:
                        for x1 in gr[y]:
                            A.add(x1)
                            qu.append(x1)

                    done.add(y)

                if  A.isdisjoint(B) == False:
                    return False
        
        return A.isdisjoint(B)
                
                
        
        
        
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if len(dislikes) == 0:
            return True
        seenA = set()
        seenB = set()
        seen = set()
        ref = dict()
        stack = []
        for i in range(1, N+1):
            ref[i] = []
        for l in dislikes:
            s, t = l[0], l[1]
            ref[s].append(t)
            ref[t].append(s)
        erase = []
        for i in ref:
            if len(ref[i]) == 0:
                erase.append(i)
        for i in erase:
            ref.pop(i)
        stack = list(ref.keys())
        while len(stack) != 0:
            i = stack.pop(0)
            if i in seen:
                continue
            target = seenA if i in seenA else seenB
            other = seenB if i in seenA else seenA
            target.add(i)
            seen.add(i)
            for j in ref[i]:
                stack.insert(0, j)
                if j in target:
                    return False
                else:
                    other.add(j)
        return True
                
        
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # build adjacency list
        adjList = {p : [] for p in range(1, N + 1)}
        for p1, p2 in dislikes:
            adjList[p1].append(p2)
            adjList[p2].append(p1)
        
        visited = set()
        # for each connected component, try to partition perople into two groups
        for person in range(1, N + 1):
            if person not in visited:
                # BFS
                # initialize two groups 
                groups = [set([person]), set()]
                curList = [person]
                level = 0
                while curList:
                    next = []
                    curGroup = groups[level % 2]
                    theOtherGroup = groups[(level + 1) % 2]
                    for p in curList:
                        visited.add(p)
                        for neighbor in adjList[p]:
                            # if the neighbor is already in the same group of this person
                            if neighbor in curGroup:
                                return False
                            if neighbor not in theOtherGroup:
                                theOtherGroup.add(neighbor)
                                next.append(neighbor)

                    curList = next
                    level += 1
            
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(N+1)]
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)    
        visited = [0] * (N+1)
        
        def go(node, prev, color):
            if visited[node] != 0:
                return visited[node] == color
            visited[node] = color
            for t in graph[node]:
                if t == prev:
                    continue
                if not go(t, node, -color):
                    return False
            return True
        
        for i in range(1, N+1):
            if visited[i] == 0 and not go(i, 0, 1):
                return False
        return True


from collections import defaultdict

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        edges = defaultdict(list)
        for p, c in dislikes:
            edges[p].append(c)
            edges[c].append(p)
        def dfs(i):
            colour = visited[i]
            for c in edges[i]:
                if c in visited:
                    if visited[c] != -colour:
                        return False
                else:
                    visited[c] = -colour
                    if not dfs(c):
                        return False
            return True
        
        visited = {}
        for i in range(1, N+1):
            if i not in visited:
                visited[i] = 1
                if not dfs(i):
                    return False
        return True

\"\"\"
50
[[21,47],[4,41],[2,41],[36,42],[32,45],[26,28],[32,44],[5,41],[29,44],[10,46],[1,6],[7,42],[46,49],[17,46],[32,35],[11,48],[37,48],[37,43],[8,41],[16,22],[41,43],[11,27],[22,44],[22,28],[18,37],[5,11],[18,46],[22,48],[1,17],[2,32],[21,37],[7,22],[23,41],[30,39],[6,41],[10,22],[36,41],[22,25],[1,12],[2,11],[45,46],[2,22],[1,38],[47,50],[11,15],[2,37],[1,43],[30,45],[4,32],[28,37],[1,21],[23,37],[5,37],[29,40],[6,42],[3,11],[40,42],[26,49],[41,50],[13,41],[20,47],[15,26],[47,49],[5,30],[4,42],[10,30],[6,29],[20,42],[4,37],[28,42],[1,16],[8,32],[16,29],[31,47],[15,47],[1,5],[7,37],[14,47],[30,48],[1,10],[26,43],[15,46],[42,45],[18,42],[25,42],[38,41],[32,39],[6,30],[29,33],[34,37],[26,38],[3,22],[18,47],[42,48],[22,49],[26,34],[22,36],[29,36],[11,25],[41,44],[6,46],[13,22],[11,16],[10,37],[42,43],[12,32],[1,48],[26,40],[22,50],[17,26],[4,22],[11,14],[26,39],[7,11],[23,26],[1,20],[32,33],[30,33],[1,25],[2,30],[2,46],[26,45],[47,48],[5,29],[3,37],[22,34],[20,22],[9,47],[1,4],[36,46],[30,49],[1,9],[3,26],[25,41],[14,29],[1,35],[23,42],[21,32],[24,46],[3,32],[9,42],[33,37],[7,30],[29,45],[27,30],[1,7],[33,42],[17,47],[12,47],[19,41],[3,42],[24,26],[20,29],[11,23],[22,40],[9,37],[31,32],[23,46],[11,38],[27,29],[17,37],[23,30],[14,42],[28,30],[29,31],[1,8],[1,36],[42,50],[21,41],[11,18],[39,41],[32,34],[6,37],[30,38],[21,46],[16,37],[22,24],[17,32],[23,29],[3,30],[8,30],[41,48],[1,39],[8,47],[30,44],[9,46],[22,45],[7,26],[35,42],[1,27],[17,30],[20,46],[18,29],[3,29],[4,30],[3,46]]
return T
\"\"\"
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        g = collections.defaultdict(list)
        for p1, p2 in dislikes:
            g[p1].append(p2)
            g[p2].append(p1)
        colored = {}
        # print(g)
        def check(p, color):
            if p in colored:
                if not colored[p] == color:
                    print(p, color, colored)
                    return False
                else:
                    return True
            colored[p] = color
            for nb in g[p]:
                if not check(nb, -color):
                    return False
            return True
        for p in range(1, N + 1):
            if p not in colored and not check(p, 1):
                # print(p, colored)
                return False
        return True

class UnionFind:
    def __init__(self):
        self.reps = {}
        self.ranks = {}
    
    def makeset(self, x):
        self.reps[x] = x
        self.ranks[x] = 0
    
    def find(self, x):
        if self.reps[x] != x:
            self.reps[x] = self.find(self.reps[x])
        return self.reps[x]
    
    def union(self, x, y):
        rep_x = self.find(x)
        rep_y = self.find(y)
        if self.ranks[rep_x] > self.ranks[rep_y]:
            self.reps[rep_y] = rep_x
        elif self.ranks[rep_x] == self.ranks[rep_y]:
            self.reps[rep_y] = rep_x
            self.ranks[rep_x] += 1
        else:
            self.reps[rep_x] = rep_y

class Solution:
    # Union find to determine if graph is bipartite or 2 color alg would work here
    # 20 min to think of union find alg until look up the answer start: 10:33
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # they've given us a list of edges to work with 
        unionfind = UnionFind()
        for i in range(N):        
            unionfind.makeset(i+1)
        graph = {}
        for (u, v) in dislikes:
            graph.setdefault(u, [])
            graph[u].append(v)
            graph.setdefault(v, [])
            graph[v].append(u)
        
        for person in graph:
            for enemy in graph[person]:
                # intution is this:
                # every one in graph[person] should be in the same bipartite group
                rep_u = unionfind.find(person)
                rep_v = unionfind.find(enemy)
                if rep_u != rep_v:
                    unionfind.union(graph[person][0], enemy)
                else:
                    return False
        
        return True
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def visit(a, depth):     
            if a in depths:
                return (depth - depths[a]) % 2 == 0

            depths[a] = depth
            return all(visit(b, depth + 1) for b in d[a])

        d = collections.defaultdict(set)
        depths = {}
        for a,b in dislikes:
            d[a].add(b)
            d[b].add(a)

        return all(a in depths or visit(a, 0) for a in d)
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        dislike_graph = {}
        for i in range(1, N+1):
            dislike_graph[i] = []
            
        for pair in dislikes:
            a, b = pair
            dislike_graph[a].append(b)
            dislike_graph[b].append(a)
            
        
        visited = [False]*(N+1)
        color={}
        
        def dfs(i):
            if visited[i]:
                return True
            
            visited[i] = True
            for nbs in dislike_graph[i]:
                if nbs in color:
                    if color[nbs]==color[i]:
                        return False
                else:
                    color[nbs] = -color[i]
                    if not dfs(nbs):
                        return False
            return True
        

        for i in range(1, N+1):
            if visited[i]:
                continue
            color[i] = 1
            if not dfs(i):
                return False
        
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        NOT_COLORED, BLUE, GREEN = 0, 1, -1
        
        if N == 1 or not dislikes:
            return True
        
        dislike_table = collections.defaultdict(list)
        color_table = [NOT_COLORED for _ in range(N+1)]
        
        for i, j in dislikes:  ###undirected graph
            dislike_table[i].append(j)
            dislike_table[j].append(i)
        
        def dfs(node, color):
            color_table[node] = color
            for adj in dislike_table[node]:
                
                if color_table[adj] == color:
                    return False
                if color_table[adj] == NOT_COLORED and not dfs(adj, -color):
                    return False
                
            return True
        
        
        for person_id in range(1, N+1):
            if color_table[person_id] == NOT_COLORED and not dfs(person_id, BLUE):
                return False
            
        return True
        


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adj = defaultdict(set)
        for u,v in dislikes:
            adj[u].add(v)
            adj[v].add(u)
        color = [-1] * (N + 1)
        for i in range(1,N+1):
            if color[i] == -1:
                color[i] = 0
                Q = [i]
                while Q:
                    new = []
                    for cur in Q:
                        for nxt in adj[cur]:
                            if color[nxt] == color[cur]:
                                return False
                            if color[nxt] == -1:
                                color[nxt] = 1- color[cur]
                                new.append(nxt)
                    Q = new
        return True

from collections import defaultdict, deque
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(set)
        for dislike in dislikes:
            graph[dislike[0]].add(dislike[1])
            graph[dislike[1]].add(dislike[0])
        
        colors = [-1 for i in range(N + 1)]
        queue = deque()
        for i in range(1, N):
            if colors[i] == -1:
                queue.append(i)
                colors[i] = 0
                while len(queue) > 0:
                    cur = queue.popleft()
                    for neighbor in graph[cur]:
                        if colors[neighbor] == -1:
                            colors[neighbor] = 1 - colors[cur]
                            queue.append(neighbor)
                        elif colors[neighbor] == colors[cur]:
                                return False
                    
        return True

# 886. Possible Bipartition

import collections
class Solution:
    
    def __init__(self):
        self.colors = []
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        not_colored = 2
        self.colors = [not_colored] * (N + 1)
        
        graph = collections.defaultdict(list)
        
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
            
        for n in range(1, N): 
            if colors[n] == not_colored and not self.dfs(graph, n, 1):
                return False
            
        return True
        
    def dfs(self, graph, vertex, color):
        self.colors[vertex] = color
        
        for u in graph[vertex]:
            if self.colors[vertex] == colors[u]:
                return False
            if self.colors[u] == 2 and not self.dfs(graph, u, not color):
                return False
        
        return True
    
    
\"\"\"
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    780 ms, faster than 28.52%
\"\"\"


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"

        connections = collections.defaultdict(list)

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, seen) == False:
                    return False
        return True

    def check(self, connections, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = connections[pop]
            for v in vertices:
                q.append((v, -color))
        return True


\"\"\"
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    660 ms, faster than 53.79%
\"\"\"


class Solution2(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, 1, seen) == False:
                    return False
        return True

    def check(self, connections, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = connections[node]
        for v in vertices:
            if self.check(connections, v, -color, seen) == False:
                return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        NOT_COLORED, RED, BLUE = 0, 1, -1 
        colors = {p: NOT_COLORED for p in range(1, N + 1)}
        graph = collections.defaultdict(list)
        
        def dfs(person, color):
            colors[person] = color
            for neighbor in graph[person]:
                if colors[neighbor] == color:
                    return False
                if colors[neighbor] == NOT_COLORED and not dfs(neighbor, -color):
                    return False
            return True
        
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
        
        for i in range(1, N + 1):
            if colors[i] == NOT_COLORED and not dfs(i, RED):
                return False
        
        return True
            
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(set)
        for i, j in dislikes:
            graph[i].add(j)
            graph[j].add(i)
        
        color = dict()
        
        for i in range(1,N+1):
            if i not in color:
                if not self.dfs(i, color, graph, c=0):
                    return False
        # print(color)        
        return True        
    
    def dfs(self, idx, color, graph, c):
        # print((idx,c))
        color[idx] = c
        newc = 0 if c == 1 else 1
        for i in graph[idx]:
            if i not in color:
                if not self.dfs(i, color, graph, newc):
                    return False
            else:
                if color[i] == color[idx]:
                    return False
        return True   


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        edges = collections.defaultdict(list)
        for d in dislikes:
            edges[d[0]].append(d[1])
            edges[d[1]].append(d[0])
        
        def dfs(i,col):
            if i in color:
                if color[i]!=col: return False
                else: return True
            else: color[i] = col
            
            new = 1 if col==0 else 0
            for e in edges[i]:
                if not dfs(e,new): return False
            return True
            
        
        color = {}
        for i in range(N):
            if i not in color and not dfs(i,0): return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        edges = {i:[] for i in range(1, N + 1)}
        for a, b in dislikes:
            edges[a].append(b)
            edges[b].append(a)
        
        groups = {}
        stack = []
        for i in range(1, N + 1):
            if i in groups:
                continue
            stack.append(i)
            groups[i] = 0
            while stack:
                cur = stack.pop()
                for dis in edges[cur]:
                    if dis not in groups:
                        stack.append(dis)
                        groups[dis] = groups[cur] ^ 1     
                    elif groups[dis] == groups[cur]:
                        return False
        return True
                       
                    
                     
                
                
                
                


from collections import deque
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = {i:[] for i in range(1,N+1)}
        for a,b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        self.is_possible = True
        self.visited = [0]*(N+1)
        self.color = [0]*(N+1)
        for i in range(1,N+1):
            if not self.visited[i]:
                self.color[i] = 1
                self.traverse(graph, i)
        return self.is_possible
    
    def traverse(self, graph, node):
        queue = deque([node])
        while queue:
            node = queue.popleft()
            self.visited[node] = 1
            color = self.color[node]
            for neigh in graph[node]:
                if color == self.color[neigh]:
                    self.is_possible = False
                    return
                if not self.visited[neigh] and not neigh in queue:
                    self.color[neigh] = -color
                    queue.append(neigh)


class Solution:
    # Essentially check whether the graph is bipartitable and dislikes indicate the edges.
    # Build the adjacent graph first.
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adjacents = collections.defaultdict(list)
        for a, b in dislikes:
            adjacents[a].append(b)
            adjacents[b].append(a)
        # bipartite check
        colored = {}
        for i in range(N):
            if i not in colored:
                colored[i] = 0
                stack = [i]
                while stack:
                    node = stack.pop()
                    for neighbor in adjacents[node]:
                        if neighbor not in colored:
                            colored[neighbor] = 1 - colored[node]
                            stack.append(neighbor)
                        if colored[neighbor] == colored[node]:  # conflict color
                            return False
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        color = [-1 for _ in range(N + 1)]
        g = collections.defaultdict(set)
        for a, b in dislikes:
            g[a].add(b)
            g[b].add(a)
        visited = set()
        for i in range(1, N + 1):
            if i not in visited:
                q = collections.deque()
                q.append(i)
                visited.add(i)
                color[i] = 0
                while q:
                    size = len(q)
                    while size > 0:
                        node = q.popleft()
                        for nei in g[node]:
                            if nei not in visited:
                                q.append(nei)
                                visited.add(nei)
                                color[nei] = 1 - color[node]
                            else:
                                if color[nei] != 1 - color[node]:
                                    return False
                        size -= 1
        return len(set(color)) == 3

# 886. Possible Bipartition

import collections
class Solution:
    
    def __init__(self):
        self.colors = []
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        not_colored = 2
        self.colors = [not_colored] * (N + 1)
        
        graph = collections.defaultdict(list)
        
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
            
        for n in range(1, N): 
            if colors[n] == not_colored and not self.dfs(graph, n, 1):
                return False
            
        return True
        
    def dfs(self, graph, vertex, color):
        self.colors[vertex] = color
        
        for u in graph[vertex]:
            if colors[vertex] == colors[u]:
                return False
            if colors[u] == 2 and not self.dfs(graph, u, not color):
                return False
        
        return True
    
    
\"\"\"
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    780 ms, faster than 28.52%
\"\"\"


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"

        connections = collections.defaultdict(list)

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, seen) == False:
                    return False
        return True

    def check(self, connections, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = connections[pop]
            for v in vertices:
                q.append((v, -color))
        return True


\"\"\"
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    660 ms, faster than 53.79%
\"\"\"


class Solution2(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, 1, seen) == False:
                    return False
        return True

    def check(self, connections, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = connections[node]
        for v in vertices:
            if self.check(connections, v, -color, seen) == False:
                return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adjL = defaultdict(list)
        for u, v in dislikes:
            adjL[u].append(v)
            adjL[v].append(u)
        
        memo = [-1]*(N+1) #-1: not seen, 0: group 1, 1: group 2
        def df(src, shouldBe):
            if memo[src]!=-1:
                return memo[src]==shouldBe
            memo[src] = shouldBe
            for dst in adjL[src]:
                if not df(dst, shouldBe^1):
                    return False
            return True
        
        for i in range(1, N+1):
            if memo[i]==-1 and not df(i, 0):
                return False
        return True
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        graph = {i : [] for i in range(1, N + 1)}
        
        for dislike in dislikes:
            u, v = dislike
            graph[u].append(v)
            graph[v].append(u)
        visited = collections.defaultdict(int)
        queue = collections.deque([])
        color = 0
        for i in range(1, N + 1):
            if i not in visited:
                queue.append(i)
                visited[i] = 0
            while queue:
                node = queue.popleft()
                clr = visited[node]
                for nei in graph[node]:
                    if nei not in visited:
                        visited[nei] = ~clr
                        queue.append(nei)
                    else:
                        if visited[nei] == clr:
                            return False
        return True
                        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        x={i:[] for i in range(1,N+1)}
        for i,j in dislikes:
            x[i].append(j)
            x[j].append(i)
        colour=[-1]*N
        for i in range(1,N+1):
            if colour[i-1]==-1:
                colour[i-1]=0
                q=[i]
                while q:
                    node=q.pop(0)
                    for j in x[node]:
                        if colour[node-1]==colour[j-1]:
                            return False
                        if colour[j-1]==-1:
                            colour[j-1]=colour[node-1]^1
                            q.append(j)
        return True

import collections
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # build graph
        graph = collections.defaultdict(list)
        for fr, to in dislikes:
            graph[fr].append(to)
            graph[to].append(fr)

        group = collections.defaultdict(bool) # true group and false group
        curr_group = True
        for i in range(1, N+1):
            if i not in group:
                q = collections.deque([i])
                group[i] = curr_group
                while q:
                    for _ in range(len(q)):
                        node = q.popleft()
                        # look at neighbors
                        for nei in graph[node]:
                            if nei in group and group[nei] == curr_group:
                                return False
                            elif nei not in group:
                                q.append(nei)
                                group[nei] = not curr_group
                    curr_group = not curr_group
        return True


# 886. Possible Bipartition

class Solution1:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        g = collections.defaultdict(list)
        for u, v in dislikes:
            g[u].append(v)
            g[v].append(u)
            
        color = {}
        def dfs(node, c=0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c^1) for nei in g[node])
        
        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)
    
    
\"\"\"
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    780 ms, faster than 28.52%
\"\"\"


class Solution2(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, seen) == False:
                    return False
        return True

    def check(self, connections, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = connections[pop]
            for v in vertices:
                q.append((v, -color))
        return True


\"\"\"
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    660 ms, faster than 53.79%
\"\"\"


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, 1, seen) == False:
                    return False
        return True

    def check(self, connections, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = connections[node]
        for v in vertices:
            if self.check(connections, v, -color, seen) == False:
                return False
        return True

from queue import Queue

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        self.g = self.build_graph(dislikes)
        
        self.visited = set()
        self.colors = dict()
        
        
        
        for u in self.g.keys():
            q = Queue()
            q.put(u)
            if u not in self.colors:
                self.colors[u] = 0
            
            while not q.empty():        
                cur = q.get()
                self.visited.add(cur)
                
                for v in self.g[cur]:
                    if v in self.colors and self.colors[v] == self.colors[cur]:
                        return False
                    
                    if v not in self.visited:
                        self.colors[v] = self.colors[cur] ^ 1
                        self.visited.add(v)
                        q.put(v)
                
        
        return True
    
            
        
    def build_graph(self, dislikes):
        g = collections.defaultdict(set)
        
        for u,v in dislikes:
            g[u].add(v)
            g[v].add(u)
        
        return g

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = []
        for person in range(N+1):
            graph.append([])
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        seen = {}
        for i in range(1, N+1):
            if i not in seen:
                if self.bfs(graph, i, seen) == False:
                    return False
        return True
    
    def bfs(self, graph, person, seen):
        q = [(person, 1)]
        while q:
            person, color = q.pop(0)
            if person in seen:
                if seen[person] != color:
                    return False
                continue
            seen[person] = color
            vertices = graph[person]
            for v in vertices:
                q.append((v, -color))
        return True

import collections
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(curr, current_color):
            color[curr] = current_color
            for next in graph[curr]:
                if color[next] == None:
                    dfs(next, not current_color)
                elif color[next] == current_color:
                    return False
            return True

        color = [None] * (N + 1)
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        for n in range(1, N + 1):
            if color[n] == None:
                if not dfs(n, True):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        colors = [0] * (N + 1)
        
        from collections import defaultdict
        g = defaultdict(set)
        for dislike in dislikes:
            g[dislike[0]].add(dislike[1])
            g[dislike[1]].add(dislike[0])
            
        from collections import deque
        q = deque()
        
        for i in range(1, N + 1):
            if i not in g:
                colors[i] = 1
                
            if colors[i]:
                continue
            
            colors[i] = 1
            q.append(i)
            while q:
                cur = q.popleft()
                for neighbor in g[cur]:
                    if colors[neighbor]:
                        if colors[neighbor] == colors[cur]:
                            return False
                        continue
                    colors[neighbor] = 1 if colors[cur] == -1 else -1
                    q.append(neighbor)
                    
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        '''
        def dfs(curr, curr_color):
            color[curr] = curr_color
            for next in graph[curr]:
                dfs(next, not curr_color)
        '''
        
        curr_color = True
        graph = collections.defaultdict(list)
        color = [None]  * (N+1)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        for n in range(1, N+1):
            if color[n] == None:
                color[n] = curr_color
                queue = collections.deque([n])
                while queue:
                    for _ in range(len(queue)):
                        curr = queue.popleft()
                        for next in graph[curr]:
                            if color[next] == None:
                                color[next] = not curr_color
                                queue.append(next)
                            elif color[next] == curr_color:
                                return False
                    curr_color = not curr_color
        return True

class Solution:
    def possibleBipartition(self, N, dislikes):
        NOT_COLORED, BLUE, GREEN = 0, 1, -1 # Constant defined for color drawing to person
        def helper( person_id, color ):
            color_table[person_id] = color # Draw person_id as color
            for the_other in dislike_table[ person_id ]: # Draw the_other, with opposite color, in dislike table of current person_id
                if color_table[the_other] == color: # the_other has the same color of current person_id
                    return False
                if color_table[the_other] == NOT_COLORED and (not helper( the_other, -color)):
                    # Other people can not be colored with two different colors. 
\t\t\t\t\t# Therefore, it is impossible to keep dis-like relationship with bipartition.
                    return False
                    
            return True
\t\t
        
        # each person maintain a list of dislike
        dislike_table = collections.defaultdict( list )
        
        # cell_#0 is dummy just for the convenience of indexing from 1 to N
        color_table = [ NOT_COLORED for _ in range(N+1) ]
        
        for p1, p2 in dislikes:
            
            # P1 and P2 dislike each other
            dislike_table[p1].append( p2 )
            dislike_table[p2].append( p1 )
            
        
        # Try to draw dislike pair with different colors in DFS
        for person_id in range(1, N+1):
            
            if color_table[person_id] == NOT_COLORED and (not helper( person_id, BLUE)):
                # Other people can not be colored with two different colors. 
\t\t\t\t# Therefore, it is impossible to keep dis-like relationship with bipartition.
                return False 
        
        return True


# from collections import defaultdict
# class Solution:
#     def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
#         graph = defaultdict(set)
        
#         for relation in dislikes:
#             graph[relation[0]].add(relation[1])
#             graph[relation[1]].add(relation[0])
            
class Solution:
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        if len(dislikes) < 3:
            return True
        
        graph = collections.defaultdict(list)
        color = {}    # -1 means red, 1 blue, 0 no color
        nodes = set()
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
            nodes.add(x)
            nodes.add(y)
                    
        for node in nodes:
            if node not in color:
                color[node] = 1
                q = collections.deque([node])
                while q:
                    cur = q.popleft()
                    cur_color = color[cur]
                    for nei in graph[cur]:
                        if nei not in color:
                            color[nei] = -cur_color
                            q.append(nei)
                        if color[nei] == cur_color:
                            return False
                        elif color[nei] == -cur_color:  # visited
                            continue
                        #color[nei] = -cur_color
                        
        return True
            
        
            
        
        

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes: return True
        
        v = collections.defaultdict(int)
        for a, b in dislikes:
            v[a] += 1
            v[b] += 1
        
        d = []
        for a, b in dislikes:
            if v[a] == 1 and v[b] == 1:
                continue
            d.append([a, b])
            
        d.sort(key = lambda x:x[0])
        c1, c2 = set(), set()
        c1.add(d[0][0])
        c2.add(d[0][1])
        for a, b in d[1:]:
            if (a in c1 and b in c1) or (a in c2 and b in c2):
                return False
            if a in c1:
                c2.add(b)
            elif a in c2:
                c1.add(b)
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(lambda: [])
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        visited = {}
        def visit(index: int, a: int) -> bool:
            if a in visited:
                return (index - visited[a]) % 2 == 0
            visited[a] = index
            for b in graph[a]:
                if not visit(index + 1, b): return False
            return True
        for a in range(1, N + 1):
            if a not in visited and not visit(0, a): return False
        return True
    
    def possibleBipartition1(self, N: int, dislikes: List[List[int]]) -> bool:
        if len(dislikes) == 0: return True
        group1 = defaultdict(lambda: 0)
        group2 = defaultdict(lambda: 0)
        def bothInGroup(group: set, a: int, b: int) -> bool:
            return group[a] > 0 and group[b] > 0
        
        def helper(group1Person: int, group2Person: int, index: int) -> bool:
            #print(\"helper\", index)
            group1[group1Person] += 1
            group2[group2Person] += 1
            #print(list(filter(lambda x: x[1] > 0, group1.items())))
            #print(list(filter(lambda x: x[1] > 0, group2.items())))
            if index == len(dislikes): return True
            a, b = dislikes[index]
            #print(\"loop\", index, a, b)
            if bothInGroup(group1, a, b) or bothInGroup(group2, a, b):
                group1[group1Person] -= 1
                group2[group2Person] -= 1
                return False
            if group1[a] > 0 or group2[b] > 0:
                if helper(a, b, index + 1): return True
            elif group2[a] > 0 or group1[b] > 0:
                if helper(b, a, index + 1): return True
            else:
                if helper(a, b, index + 1): return True
                if helper(b, a, index + 1): return True
            group1[group1Person] -= 1
            group2[group2Person] -= 1
            return False
        
        return helper(dislikes[0][0], dislikes[0][1], 1)

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N, dislikes):
        graph = defaultdict(set)
        for u, v in dislikes:
            graph[u].add(v)
            graph[v].add(u)
        color = dict()
        def dfs(node):
            for nei in graph[node]:
                if nei in color:
                    if color[nei] == color[node]:
                        return False
                else:
                    color[nei] = color[node] ^ 1
                    if not dfs(nei):
                        return False
            return True
        for node in range(1, N+1):
            if node not in color:
                color[node] = 0
                if not dfs(node):
                    return False
        return True
    
# class Solution:
#     def possibleBipartition(self, N, dislikes):
#         graph = [[] for _ in range(N+1)]
#         for u, v in dislikes:
#             graph[u].append(v)
#             graph[v].append(u)
#         color = dict()
#         def dfs(node):
#             for nei in graph[node]:
#                 if nei in color:
#                     if color[nei] == color[node]:
#                         return False
#                 else:
#                     color[nei] = color[node] ^ 1
#                     if not dfs(nei):
#                         return False
#             return True
#         for node in range(1, N+1):
#             if node not in color:
#                 color[node] = 0
#                 if not dfs(node):
#                     return False
#         return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        self.color = {}
        self.adj = {}
        for x,y in dislikes:
            if x not in self.adj:
                self.adj[x] = []
            if y not in self.adj:
                self.adj[y] = []
            self.adj[x].append(y)
            self.adj[y].append(x)
            
        self.flag = True
        def visit(x,c):
            self.color[x] = c
            if c == 0:
                n_c = 1
            else:
                n_c = 0
            for y in self.adj[x]:
                if y not in self.color:
                    visit(y,n_c)
                else:
                    if self.color[y] == c:
                        self.flag = False
        for x,y in dislikes:
            if x not in self.color:
                visit(x,0)
            if y not in self.color:
                visit(y,0)
        return self.flag


from collections import deque
class Solution:
    
    def expandColorBFS(self, start, graph, colors):
        if colors[start] != 0:
            return True
        q = deque()
        q.append(start)
        colors[start] = -1
        while q:
            cur = q.popleft()
            for neighbour in graph[cur]:
                if colors[neighbour] == 0:
                    q.append(neighbour)
                    colors[neighbour] = -colors[cur]
                elif colors[cur] == colors[neighbour]:
                    return False
        return True
    
    def expandColorDFS(self, cur, graph, colors, cur_color):
        if colors[cur] != -1:
            return cur_color == colors[cur]
        colors[cur] = cur_color
        neighbour_color = 0 if colors[cur] == 1 else 1
        for neighbour in graph[cur]:
            if not self.expandColorDFS(neighbour, graph, colors, neighbour_color):
                return False
        return True
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # -1 unvisited, 0 and 1 are the 2 groups
        colors = [0 for _ in range(N+1)]
        graph = defaultdict(set)
        for dislike in dislikes:
            graph[dislike[0]].add(dislike[1])
            graph[dislike[1]].add(dislike[0])
        
        for idx in range(1, N+1):
            if not self.expandColorBFS(idx, graph, colors):
                return False
        
        return True
        
        # for each dislike a,b
        # if we want a's group to differ from b's group


from collections import deque
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]):
        graph = defaultdict(deque)
        group = Counter()
        visited = Counter()
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        for j in range(1,n):
            if(visited[j]==0):
                stack = deque([j])
                while(stack):
                    ele = stack.pop()
                    for i in graph[ele]:
                        if(visited[i]==0):
                            stack.append(i)
                            visited[i] = 1
                            group[i] = 1-group[ele]
                        else:
                            if(group[i]!=1-group[ele]):
                                return False
        return True

from collections import deque
class Solution:
    
    def expandColorBFS(self, start, graph, colors):
        if colors[start] != -1:
            return True
        q = deque()
        q.append(start)
        colors[start] = 0
        while q:
            cur = q.popleft()
            for neighbour in graph[cur]:
                if colors[neighbour] == -1:
                    q.append(neighbour)
                    colors[neighbour] = 0 if colors[cur] == 1 else 1
                elif colors[cur] == colors[neighbour]:
                    return False
        return True
    
    def expandColorDFS(self, cur, graph, colors, cur_color):
        if colors[cur] != -1:
            return cur_color == colors[cur]
        colors[cur] = cur_color
        neighbour_color = 0 if colors[cur] == 1 else 1
        for neighbour in graph[cur]:
            if not self.expandColorDFS(neighbour, graph, colors, neighbour_color):
                return False
        return True
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # -1 unvisited, 0 and 1 are the 2 groups
        colors = [-1 for _ in range(N+1)]
        graph = defaultdict(set)
        for dislike in dislikes:
            graph[dislike[0]].add(dislike[1])
            graph[dislike[1]].add(dislike[0])
        
        for idx in range(1, N+1):
            if colors[idx] == -1:
                if not self.expandColorDFS(idx, graph, colors, 0):
                    return False
        
        return True
        
        # for each dislike a,b
        # if we want a's group to differ from b's group


class Solution:
    def possibleBipartition(self, N, dislikes):
        graph = defaultdict(list)
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)          
        def dfs(graph, colorGraph, node, color):
            colorGraph[node] = color
            for adj in graph[node]:
                if colorGraph[adj] == color:
                    return False
                if colorGraph[adj] == 0:
                    if not dfs(graph, colorGraph, adj, -color):
                        return False
            return True     
        colorGraph=[0]*(N+1)  
        for i in range(1,N):
            if colorGraph[i] == 0:
                if not dfs(graph, colorGraph, i, 1):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        
        colour = {}
        def dfs(node, c = 0):
            if node in colour:
                return colour[node] == c
            colour[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])
        
        return all(dfs(node) 
                   for node in range(1, N + 1) 
                   if node not in colour)


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N == 1 or not dislikes:
            return True
        
        g = defaultdict(set)
        for a, b in dislikes:
            g[a].add(b)
            g[b].add(a)
        
        color = [-1] * (N + 1)
        
        def dfs(i, c):
            color[i] = c
            for nxt in g[i]:
                if color[nxt] != -1 and color[nxt] == c:
                    return False
                if color[nxt] == -1 and not dfs(nxt, c ^ 1):
                    return False
            return True
        
        for i in range(1, N + 1):
            if color[i] == -1 and not dfs(i, 0):
                return False
        
        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        groups=defaultdict(list)
        for a,b in dislikes:
            groups[a].append(b)
            groups[b].append(a)
        
        colors={}
        def dfs(node,c=0):
            if node in colors:
                return colors[node]==c
            colors[node]=c
            return all(dfs(nei,1-c) for nei in groups[node])
        
        return all(dfs(node) for node in range(1,N+1) if node not in colors)

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adj=defaultdict(list)
        for u,v in dislikes:
            adj[u].append(v)
            adj[v].append(u)
        colors={}
        def dfs(node,color):
            if node in colors:
                return colors[node]==color
            colors[node]=color
            return all(dfs(u,1-color) for u in adj[node])
        return all(dfs(u,0) for u in range(1,N+1) if u not in colors )


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(set)
        
        for e in dislikes:
            u, v = e
            graph[u].add(v)
            
            # TODO map in both directons? I think so
            graph[v].add(u)

        print(graph)



        visited = set()

        a = set()
        b = set()

        for n in range(1, N):
            queue = deque([n])
                        
            while queue:
                u = queue.popleft()

                if u in visited:
                    continue

                visited.add(u)
                
                if len(graph[u] & a) == 0:
                    a.add(u)
                elif len(graph[u] & b) == 0:
                    b.add(u)
                else:
                    return False

                for v in graph[u]:
                    if v in visited:
                        continue

                    queue.append(v)

        print(a, b)
        
        return True

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        graph = defaultdict(list)
        
        for _from, to in dislikes:
            graph[_from].append(to)
            graph[to].append(_from)
            
        colors = {}
        
        for i in range(1,N+1):
            if i not in colors and i <= len(graph)-1:
                stack = [(i, True)]
                
                while stack:
                    keys, color = stack.pop()
                    colors[keys] = color
                    
                    for adj in graph[keys]:
                        if adj in colors:
                            if colors[adj] == colors[keys]:

                                return False
                        else:
                            stack.append((adj, not colors[keys]))
        return all([colors[i] != all(colors[j] for j in graph[i]) for i in colors if graph[i]!=[]])
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        \"\"\"
          put everyone in an unassigned set
          pick arbitrary unassigned person put them into arbitrary group
            DFS walk dislikes links assigning people to correct group, fail if impossible

          return true if we succeed

          extra space: O(N + dislikes.length)
              O(N)  to store unassigned people
              O(dislikes.length)  to map people to their dislikes
              stack with at most O(dislikes.length)

          time: O(N + dislikes.length)
             O(dislikes.length) walk once to map people to dislikes
                     handle
             O(N) each person added to a group once
             O(dislikes.length) each person's dislikes handled once when they're added to group
p        \"\"\"
        unassigned = set(range(1, N+1))
        personal_dislikes = {}
        def add_dislike(a, b):
            dis = personal_dislikes.get(a, [])
            dis.append(b)
            personal_dislikes[a] = dis

        for [a, b] in dislikes:
            add_dislike(a, b)
            add_dislike(b, a)

        # map members to `True` or `False` to represent two groups
        group = {}
        while len(unassigned) > 0:
            person = unassigned.pop()
            group[person] = True
            if person not in personal_dislikes:
                continue
            stack = [(False, enemy) for enemy in personal_dislikes[person]]
            while stack:
                group_choice, p = stack.pop()
                if p in group:
                    if group[p] != group_choice:
                        return False
                else:
                    group[p] = group_choice
                    unassigned.remove(p)
                    for enemy in personal_dislikes[p]:
                        stack.append( (not group_choice, enemy) )

        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes: 
            return True
        
        g = defaultdict(list)    
        for x, y in dislikes:
            g[x].append(y)
            g[y].append(x)
            
        groups = {}
        def dfs(curr, i):
            if curr in groups:
                return groups[curr] == i
            
            groups[curr] = i
            return all(dfs(nb, not i) for nb in g[curr])
        
        return all(dfs(x, groups.get(x, False)) for x, _ in dislikes)

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        G, colors = defaultdict(list), defaultdict(lambda : 0)
        for u,v in dislikes:
            G[u].append(v)
            G[v].append(u)
        
        def dfs(u, color):
            if u in colors:
                return colors[u] == color
            colors[u] = color
            return all((dfs(v, -color) for v in G[u]))
        
        
        return all((dfs(v, 1) for v in range(1, N+1) if v not in colors))
        


def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n

    for start in range(n):
        if color[start] == -1:
            color[start] = 0
            stack = [start]

            while stack:
                parent = stack.pop()

                for child in graph[parent]:
                    if color[child] == -1:
                        color[child] = 1 - color[parent]
                        stack.append(child)
                    elif color[parent] == color[child]:
                        return False

    return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(N)]
        for u, v in dislikes:
            u -= 1
            v -= 1
            graph[u].append(v)
            graph[v].append(u)
        return is_bipartite(graph)

class Solution:
    def createGraph(self,N,dislikes):
        # create undirected graph, edgeList
        adjList = {}
        
        # get base adjList
        baseSet = set()
        
        for vertex in range(1,N+1):
            adjList[vertex] = set()
            
        # remove non valid edges
        for v,v1 in dislikes:
            adjList[v].add(v1)
            adjList[v1].add(v)
        
        for i in adjList.keys(): print(i , \" \" , adjList[i])
        return adjList
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adjList = self.createGraph(N,dislikes)
        
        def dfs(currentLoc,adjList,colored,color):
            colored[currentLoc] = color
            
            for adj in adjList[currentLoc]:
                if adj not in colored:
                    if not dfs(adj,adjList,colored, not color): return False
                else:
                    if colored[adj] == color: return False
                    
            return True
                    
                    
                
        colored = {}
        color = 1
        for i in range(1,N+1):
            if i not in colored:
                if not dfs(i,adjList,colored,color): return False
        return True
        
            
            
            
            
            
            
            

        
        
        
        
            
        

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        h=collections.defaultdict(list)
        if dislikes==[]:
            return True
        for i in dislikes:
            h[i[0]].append(i[1])
            h[i[1]].append(i[0])
        k=set()
        for j in list(h.keys()):
            if j in k:
                continue
            v=set()
            c=set()
            q=deque()
            q.append((j,1))
            while q:
                x=q.popleft()
                if x[0] in v:
                    if x[0] in c:
                        if x[1]==1:
                            continue
                        else:
                            return False
                    else:
                        if x[1]==2:
                            continue
                        else:
                            return False
                v.add(x[0])
                k.add(x[0])
                if x[1]==1:
                    c.add(x[0])
                for i in h[x[0]]:
                    if x[1]==1:
                        q.append((i,2))
                    else:
                        q.append((i,1))
        return True


# benchmarking accepted solution
class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)

class Solution:
    def odd_cycle_exists(self, person_to_disliked_persons, person_visited, person, level):
        if (person_visited[person]):
            if (level - 1 != person_visited[person]):
                return (level - person_visited[person]) % 2
        else:
            person_visited[person] = level
            level += 1
            
            
            for next_person in person_to_disliked_persons[person]:
                if (self.odd_cycle_exists(person_to_disliked_persons, person_visited, next_person, level)):
                    return True
                
        return False
    
    
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        N += 1
        person_visited = [0] * N
        person_to_disliked_persons = [set() for i in range(N)]
        
        
        for dislike in dislikes:
            person_to_disliked_persons[dislike[0]].add(dislike[1])
            person_to_disliked_persons[dislike[1]].add(dislike[0])
            
            
        for i in range(1, N):
            if (person_visited[i] == 0 and self.odd_cycle_exists(person_to_disliked_persons, person_visited, i, 1)):
                return False
            
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if len(dislikes) == 0:
            return True
        colors = [None]*N
        G = {}
        for edge in dislikes:
            if edge[0]-1 not in G:
                G[edge[0]-1] = [edge[1]-1]
            else:
                G[edge[0]-1].append(edge[1]-1)
            if edge[1]-1 not in G:
                G[edge[1]-1] = [edge[0]-1]
            else:
                G[edge[1]-1].append(edge[0]-1)
        def dfs(node, clr):
            colors[node] = clr
            if node not in G:
                return True
            for adj in G[node]:
                if colors[adj] is None:
                    if not dfs(adj, not clr):
                        return False
                elif colors[adj] == clr: 
                    return False
            return True
        for i in range(N):
            if colors[i] is None:
                if not dfs(i, True):
                    return False
        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
       
        g = defaultdict(list)    
        for x, y in dislikes:
            g[x].append(y)
            g[y].append(x)
            
        groups = {}
        def dfs(curr, i):
            if curr in groups:
                return groups[curr] == i
            
            groups[curr] = i
            return all(dfs(nb, not i) for nb in g[curr])
        
        return all(dfs(x, groups.get(x, False)) for x, _ in dislikes)

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:        
        self.graph = [[] for i in range(n)]
        for u, v in dislikes:
            self.graph[u-1].append(v-1)
            self.graph[v-1].append(u-1)
        
        self.groups = [None for i in range(n)]
        
        for i in range(n):
            if self.groups[i] == None:
                if not self.bfs(i):
                    return False
                
        return True
        
    
    def bfs(self, node):
        queue = [node]
        self.groups[node] = 0
        
        while queue:
            q = queue.pop(0)
            for node in self.graph[q]:
                if self.groups[node] == None:
                    self.groups[node] = self.groups[q]^1
                    queue.append(node)
                elif self.groups[node] == self.groups[q]:
                    return False
                    
        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for i in range(len(dislikes)):
            graph[dislikes[i][0]].append(dislikes[i][1])
            graph[dislikes[i][1]].append(dislikes[i][0])
            
            
        color = {}
        
        def dfs(node, c=0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(n, c^1) for n in graph[node])
        
        return all(dfs(x) for x in range(1, N+1) if x not in color)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        graph = collections.defaultdict(list)
        for w, v in dislikes:
            graph[w].append(v)
            graph[v].append(w)
        
        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])
        
        for node in range(1, N + 1):
            if node not in color:
                if dfs(node) == False:
                    return False
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def method1(dislikes):
            class UF:
                def __init__(self, size):
                    self.p=list(range(size))
                    
                def find(self,x):
                    if x!=self.p[x]:
                        self.p[x]=self.find(self.p[x])
                    return self.p[x]
                
                def union(self,x,y):
                    self.p[self.find(x)]=self.find(y)
                    
                def find_all(self):
                    for i in range(len(self.p)):
                        self.find(i) 
               
            if N<2 or not dislikes:
                return True
            
            dislikes=set(map(tuple,dislikes))
            #print(dislikes)
            uf=UF(N)
            for i in range(1,N+1):
                for j in range(i+1,N+1):
                    if (i,j) not in dislikes and (j,i) not in dislikes :
                        #print(i,j)
                        uf.union(i-1,j-1)
                    
            #uf.find_all()
            #print(uf.p)
            
            return len(set(uf.p))==2
        #return method1(dislikes)
    
        def method2():
            RED=0
            BLUE=1
            
            graph=collections.defaultdict(list)
            for u,v in dislikes:
                graph[u].append(v)
                graph[v].append(u)
                
            color={}
            def dfs(node,c):
                if node in color:
                    return color[node]==c
                color[node]=c
                c=BLUE if c==RED else RED
                return all(dfs(nei,c) for nei in graph[node])
            
            return all(dfs(node,RED) for node in range(1,N+1) if node not in color)
        
        return method2()


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def bfs(i):
            queue = collections.deque([(i, 0)])
            color[i] = 0
            while queue:
                person, c = queue.pop()
                for p in graph[person]:
                    if color[p] == c: return False
                    if color[p] == -1:
                        color[p] = 1 - c
                        queue.appendleft((p, 1 - c))
            return True
        
        graph = {i: [] for i in range(1, N + 1)}
        color = {i: -1 for i in range(1, N + 1)}
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        for i in range(1, N + 1):
            if color[i] == -1 and not bfs(i): return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def method1(dislikes):
            class UF:
                def __init__(self, size):
                    self.p=list(range(size))
                    
                def find(self,x):
                    if x!=self.p[x]:
                        self.p[x]=self.find(self.p[x])
                    return self.p[x]
                
                def union(self,x,y):
                    self.p[self.find(x)]=self.find(y)
                    
                def find_all(self):
                    for i in range(len(self.p)):
                        self.find(i) 
               
            if N<2 or not dislikes:
                return True
            
            dislikes=set(map(tuple,dislikes))
            #print(dislikes)
            uf=UF(N)
            for i in range(1,N+1):
                for j in range(i+1,N+1):
                    if (i,j) not in dislikes and (j,i) not in dislikes :
                        #print(i,j)
                        uf.union(i-1,j-1)
                    
            #uf.find_all()
            #print(uf.p)
            
            return len(set(uf.p))==2
        #return method1(dislikes)
    
        def method2():
            graph=collections.defaultdict(list)
            for u,v in dislikes:
                graph[u].append(v)
                graph[v].append(u)
                
            color={}
            def dfs(node,c=0):
                if node in color:
                    return color[node]==c
                color[node]=c
                return all(dfs(nei,c^1) for nei in graph[node])
            
            return all(dfs(node) for node in range(1,N+1) if node not in color)
        
        return method2()


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        #TODO
        # every connected component must be bipartite
        if len(dislikes) == 0:
            return True
        graph = {}
        for d in dislikes:
            graph[d[0]] = graph.get(d[0], [])
            graph[d[1]] = graph.get(d[1], [])
            graph[d[0]].append(d[1])
            graph[d[1]].append(d[0])
        colors = {}
    
        # DFS
        def dfs(node, c=0):
            if node in colors:
                return colors[node] == c
            
            colors[node] = c
            nc = c ^ 1
            if graph.get(node):
                return all(dfs(neigh, nc) for neigh in graph[node])
            return True
        
        return all(dfs(i, 0) for i in range(1, N+1) if i not in colors)
            
        
        # BFS
        '''visited_set = set()
        for i in range(1, N+1):
            if i in visited_set:
                continue
            colors[i] = 0
            nodes = [i]
            visited_set.add(i)
            while True:
                # at node i
                new_nodes = []
                for node in nodes:
                    neighbors = graph.get(node)
                    if neighbors is None:
                        continue
                    c = colors[node]
                    nc = c ^ 1
                    for j in neighbors:
                        if j not in colors:
                            colors[j] = nc
                            new_nodes.append(j)
                            visited_set.add(j)
                            continue
                        if colors[j] != nc:
                            return False
                nodes = new_nodes
                if len(nodes) == 0:
                    break
        
        return True'''

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adj_list = [[] for i in range(N)]
        for a,b in dislikes:
            adj_list[a-1].append(b-1)
            adj_list[b-1].append(a-1)
        
        # 0=>uncolored, 1=>first color, 2=>second color
        colors = [0 for i in range(N)]
        
        for i in range(N):
            if colors[i] != 0:
                continue
                
            # new disconnected graph
            q = [i]
            exp_color = 1
            while len(q) > 0:
                k = len(q)
                for j in range(k):
                    node = q.pop(0)
                    if colors[node] != 0 and colors[node] != exp_color:
                        return False
                    if colors[node] == exp_color:
                        continue
                    colors[node] = exp_color
                    for x in adj_list[node]:
                        q.append(x)
                        
                exp_color = 3-exp_color
                
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        c=[-1 for i in range(N)]
        if(len(dislikes)==0):
            return True
        dislikes.sort()
        el=[[] for i in range(N)]
        for i in dislikes:
            el[i[0]-1].append(i[1]-1)
            el[i[1]-1].append(i[0]-1)
        x=dislikes[0][0]
        vis=[i for i in range(N)]
        vis.remove(x)
        c[x]=0
        d=[x]
        while(d!=[]):
            f=[]
            for i in d:
                for j in el[i]:
                    if(c[j]==-1):
                        vis.remove(j)
                        c[j]=1-c[i]
                        f.append(j)
                    elif(c[j]!=1-c[i]):
                        return False
                    else:
                        continue
            d=f
            if(d==[])and(len(vis)!=0):
                d=[vis.pop()]
                c[d[0]]=0
        return True
                    


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        
        
        for a,b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
            
        color = {}
        def dfs(node, c=0):
            if node in color:
                return color[node] == c
            
            color[node] = c
            
            return all(dfs(n, c^1) for n in graph[node])
        
        return all(dfs(n) for n in range(1, N+1) if n not in color)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(set)

        for x, y in dislikes:
            graph[x].add(y)
            graph[y].add(x)
            
        color = {}
        def dfs(x, c = 0):
            if x in color:
                return color[x] == c
            color[x] = c
            return all(dfs(nei, c^1) for nei in graph[x])
            
        return all(dfs(x) for x in range(1, N+1) if x not in color)


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        colour = [None]*(N+1)
        graph = [[] for i in range(N+1)]
        
        for v,u in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        
        def dfs(node,col):
            nonlocal colour
            nonlocal graph
            if not colour[node] :
                colour[node] = col
            elif colour[node] == col:
                return True
            else:
                return False
            for i in graph[node]:
                if not dfs(i,(col+1)%2):
                    return False
            return True
        for i in range(1,N+1):
            if not colour[i] and not dfs(i,0):
                return False
        return True
                
            
        
        
        

                
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        edges = defaultdict(list)
        for start, end in dislikes:
            edges[start].append(end)
            edges[end].append(start)
        
        colored = {}
        
        for i in range(1, 1+N):
            if i not in colored:
                color = 1
                if not self.get_colors(edges, i, color, colored):
                    return False
        return True
    
    def get_colors(self, edges, start, color, colored):
        q = [(start, color)]
        
        while len(q)>0:
            node, col = q.pop(0)
            
            if node in colored:
                if colored[node] != col:
                    return False
                continue
            colored[node] = col
            new_col = 0 if col==1 else 1
            for vert in edges[node]:
                q.append((vert, new_col))
            
        return True


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

        # We can look at this as a graph problem, where we connect all the 
        # numbers with all the numbers they dislike.
        #
        # If we have any cycles of odd length, then we return False
        #
        graph = {i: [] for i in range(1, N + 1)}
        for a,b in dislikes:
          graph[a].append(b)
          graph[b].append(a)

        # part table to assign partition to each number
        part = [None for _ in range(N + 1)]
        def dfs(i, p):
          part[i] = p
          for j in graph[i]:
            if part[j] == p:
              return False
            if part[j] is None and not dfs(j, p ^ 1):
              return False
          return True

        for i in graph:
          if part[i] is None and not dfs(i, 1):
            return False
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        colors = [''] * N
        edges = [[] for _ in range(N)]
        for p1, p2 in dislikes:
            edges[p1-1].append(p2-1)
            edges[p2-1].append(p1-1)

        def dfs(i, d):
            colors[i] = 'r' if d == 0 else 'b'
            for p in edges[i]:
                if colors[p] != '':
                    if colors[p] == 'r' and d == 0: return False
                    if colors[p] == 'b' and d == 1: return False
                elif not dfs(p, (d+1)%2): return False
            return True
        for i in range(N):
            if colors[i] == '':
                if not dfs(i, 0):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        dislike_graph = collections.defaultdict(list)
        
        for dislike in dislikes:
            a, b = dislike[0], dislike[1]
            dislike_graph[a].append(b)
            dislike_graph[b].append(a)

        groups = [0]*(N+1)
        
        def can_split(cur, group):
            groups[cur] = group

            for neighbor in dislike_graph[cur]:
                if groups[neighbor] == group or \\
                (groups[neighbor] == 0 and not can_split(neighbor, -1*group)):
                    return False
            
            return True
        
        for i in range(1, N+1):
            if i not in dislike_graph:
                continue
            if groups[i] == 0 and not can_split(i, 1):

                return False
        
        return True
        

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        #TODO
        # every connected component must be bipartite
        if len(dislikes) == 0:
            return True
        graph = {}
        for d in dislikes:
            graph[d[0]] = graph.get(d[0], [])
            graph[d[1]] = graph.get(d[1], [])
            graph[d[0]].append(d[1])
            graph[d[1]].append(d[0])
        colors = {}
        
        visited_set = set()
        for i in range(1, N+1):
            if i in visited_set:
                continue
            colors[i] = 0
            nodes = [i]
            visited_set.add(i)
            while True:
                # at node i
                new_nodes = []
                for node in nodes:
                    neighbors = graph.get(node)
                    if neighbors is None:
                        continue
                    c = colors[node]
                    nc = c ^ 1
                    for j in neighbors:
                        if j not in colors:
                            colors[j] = nc
                            new_nodes.append(j)
                            visited_set.add(j)
                            continue
                        if colors[j] != nc:
                            return False
                nodes = new_nodes
                if len(nodes) == 0:
                    break
        
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        Dislike = collections.defaultdict(list)
        for dislike in dislikes:
            Dislike[dislike[0]-1].append(dislike[1]-1)
            Dislike[dislike[1]-1].append(dislike[0]-1)
        color = [-1 for i in range(N)]
        while -1 in color:
            uncolored = color.index(-1)
            q = collections.deque([uncolored])
            while q:
                i = q.popleft()
                if color[i] == -1:
                    color[i] = 0
                for d in Dislike[i]:
                    if color[d] == -1:
                        q.append(d)
                        color[d] = color[i] ^ 1
                    elif color[d] == color[i]:
                        return False
        return True

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(set)
        for pair in dislikes:
            graph[pair[0]].add(pair[1])
            graph[pair[1]].add(pair[0])
        colors = [0] * ((N) + 1)
        
        visited = set()
        def check(i):
            stack = [i]
            colors[i] = -1
            while stack:
                popped = stack.pop()
                color = colors[popped]
                visited.add(popped)
                for enemy in graph[popped]:
                    if colors[enemy] == color:
                        return False
                    colors[enemy] = -color
                    if enemy not in visited:
                        stack.append(enemy)
            return True
        for i in range(1, N+1):
            if i in visited:
                continue
            if not check(i):
                return False
        return True
        
        
                
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if(not dislikes):
            return True
        from random import sample
        adjmat={}
        for a,b in dislikes:
            adjmat[a]=adjmat.get(a,[])+[b]
            adjmat[b]=adjmat.get(b,[])+[a]
        color={i:-1 for i in range(1,N+1)}
        unvisited={i for i in range(1,N+1)}
        result=True
        while(unvisited and result):
            queue=[sample(unvisited,k=1)[0]]
            color[queue[0]]=1
            while(queue and result):
                curr=queue.pop()
                unvisited.discard(curr)
                currcolor=color[curr]
                adjcolor=0
                if(currcolor==0):
                    adjcolor=1
                if(adjmat.get(curr,0)==0):
                    continue
                for i in adjmat[curr]:
                    if i in unvisited:
                        queue.append(i)
                    if(color[i]==-1):
                        color[i]=adjcolor
                    elif(color[i]==currcolor):
                        result=False
                        break
        return result


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        relations = [None] * N
        for x in range(len(relations)):
            relations[x] = []
        
        for x in dislikes:
            a = min(x) -1
            b = max(x) -1
            relations[a].append(b)
            relations[b].append(a)
            
        # print(relations)
            
        colors = [0] * (N)
        for i,v in enumerate(relations):
            q = []
            if colors[i] == 0: q.append((i, 1))
            while q:
                (curr, selectedColor) = q.pop(0)
                if colors[curr] != 0:
                    if colors[curr] != selectedColor: return False
                    continue
                colors[curr] = selectedColor
                for n in relations[curr]:
                    q.append((n, -selectedColor))
        return True
                    
                


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(N)]
        for pair in dislikes:
            graph[pair[0]-1].append(pair[1]-1)
            graph[pair[1]-1].append(pair[0]-1)
          
        visited = {}
        def dfs(node, color):
            nonlocal visited
            visited[node] = color
            
            for child in graph[node]:
                if not child in visited:
                    if not dfs(child, not color):
                        return False
                else:
                    if visited[child] == color:
                        return False
            return True
        for i in range(N):
            if not i in visited:
                if not dfs(i, False):
                    return False
        return True
                        
            
            


class Solution1:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        
        g = collections.defaultdict(list)
        for u, v in dislikes:
            g[u].append(v)
            g[v].append(u)
            
        color = {}
        def dfs(node, c=0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c^1) for nei in g[node])
        
        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)
    
    
\"\"\"
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    780 ms, faster than 28.52%
\"\"\"


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, seen) == False:
                    return False
        return True

    def check(self, connections, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = connections[pop]
            for v in vertices:
                q.append((v, -color))
        return True


\"\"\"
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V+E)
    660 ms, faster than 53.79%
\"\"\"


class Solution2(object):
    def possibleBipartition(self, N, dislikes):
        \"\"\"
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        \"\"\"
        connections = []
        for _ in range(N+1):
            connections.append([])

        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)

        seen = {}
        for i in range(len(connections)):
            if i not in seen:
                if self.check(connections, i, 1, seen) == False:
                    return False
        return True

    def check(self, connections, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = connections[node]
        for v in vertices:
            if self.check(connections, v, -color, seen) == False:
                return False
        return True

class Solution:
    def search(self, graph, key, visited):
        stateList = [[key, 1]]
        while stateList:
            index, color = stateList.pop(0)
            if index in visited:
                if visited[index] != color:
                    return False
                continue
            visited[index] = color
            links = graph[index]
            for link in links:
                stateList.append([link, -color])
        return True
            
    def generateGraph(self, dislikes):
        graph = {}
        for a, b in dislikes:
            if a not in graph:
                graph[a] = []
            if b not in graph:
                graph[b] = []
            graph[a].append(b)
            graph[b].append(a)
        return graph
    
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = self.generateGraph(dislikes)
        
        visited = {}
        for key in graph:
            if key not in visited:
                if not self.search(graph, key, visited):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        g = defaultdict(list)
        
        for i,j in dislikes:
            g[i-1].append(j-1)
            g[j-1].append(i-1)
            
        color = [-1]*N
        
        for i in range(N):
            if color[i] == -1:
                color[i] = 0
                queue = [i]
                
            while queue:
                u = queue.pop(0)
                
                for j in g[u]:
                    
                    if color[j] == color[u]:
                        return False
                    
                    if color[j] == -1:
                        queue.append(j)
                        color[j] = 1-color[u]
                        
        return True
                
        
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        d={}
        for a,b in dislikes:
            if a not in d:
                d[a]=[]
            d[a].append(b)
            if b not in d:
                d[b]=[]
            d[b].append(a)

        vals=[-1]*(N+1)
        for i in range(1,N+1):
            if vals[i]!=-1:
                continue
            vals[i]=0
            queue=[i]
            while(queue):
                temp=[]
                for e in queue:
                    for child in d.get(e,[]):
                        if vals[e]==vals[child]:
                            return False
                        if vals[child]==-1:
                            vals[child]=1-vals[e]
                            temp.append(child)
                queue=temp
        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        pref = defaultdict(set)
        for dis in dislikes:
            a,b = dis
            pref[a].add(b)
            pref[b].add(a)
        
        to_visit = set(range(1,N+1))
        
        while to_visit:
            cur = to_visit.pop()
            
            if cur not in pref:
                pass
            else:
                
                r1 = set([cur])
                r2 = pref[cur]
                #to_visit = to_visit.difference(r2)
                L1 = r2.copy()
                L2 = set()
                
                while L1:
                    #print(r1,r2,to_visit,L1)
                    for l in L1:
                        to_visit.remove(l)
                        L = pref[l]
                        if l in r1:
                            if L.intersection(r1):
                                return False
                            else:
                                r2 = r2.union(L)
                        if l in r2:
                            if L.intersection(r2):
                                return False
                            else:
                                r1 = r1.union(L)
                        L2 = L2.union(L)
                    L2 = L2.intersection(to_visit)
                    L1 = L2
                    L2 = set()
                #print(r1,r2)
        return True



import collections

class Solution:
    def possibleBipartition(self, N, dislikes):
        NOT_COLORED, BLUE, GREEN = 0, 1, -1 # Constant defined for color drawing to person
        def helper( person_id, color ):
            color_table[person_id] = color # Draw person_id as color
            for the_other in dislike_table[ person_id ]: # Draw the_other, with opposite color, in dislike table of current person_id
                if color_table[the_other] == color: # the_other has the same color of current person_id
                    return False
                if color_table[the_other] == NOT_COLORED and (not helper( the_other, -color)):
                    # Other people can not be colored with two different colors. 
\t\t\t\t\t# Therefore, it is impossible to keep dis-like relationship with bipartition.
                    return False
            return True

        dislike_table = collections.defaultdict( list )
        
        # cell_#0 is dummy just for the convenience of indexing from 1 to N
        color_table = [ NOT_COLORED for _ in range(N+1) ]
        
        for p1, p2 in dislikes:
            
            # P1 and P2 dislike each other
            dislike_table[p1].append( p2 )
            dislike_table[p2].append( p1 )
            
        
        # Try to draw dislike pair with different colors in DFS
        for person_id in range(1, N+1):
            
            if color_table[person_id] == NOT_COLORED and (not helper( person_id, BLUE)):
                # Other people can not be colored with two different colors. 
\t\t\t\t# Therefore, it is impossible to keep dis-like relationship with bipartition.
                return False 
        
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(s):
            nonlocal doable
            visited[s] = 1
            for w in adjlist[s]:
                if visited[w] == -1:
                    visited[w] = 1
                    parent[w] = s
                    color[w] = 1 - color[s]
                    dfs(w)
                else:
                    if w != parent[s]:
                        # Odd-length cycles in graph are not amicable, but even-length cycles are ok.
                        # In dfs, back-edge having same color is sign of impossible 
                        # In BFS cross-edge across consecutive levels is ok, but not on the same level.
                        # The distance[] helps to decide this
                        if color[w] == color[s]:
                            doable = False
        n = N 
        doable = True
        visited = {x:-1 for x in range(1,n+1)}
        parent = {x:None for x in range(n)}
        # adjlist = {x:[] for x in range(1,n+1)}
        adjlist = {x:set() for x in range(1,n+1)}
        for dislike in dislikes:
            [s,d] = dislike
            # adjacency-list implementation
            # adjlist[d].append(s)
            # adjlist[s].append(d)
            # adjacency-map implementation 
            # https://algocoding.wordpress.com/2014/08/24/adjacency-list-representation-of-a-graph-python-java/
            adjlist[d].add(s)
            adjlist[s].add(d)
            # adjlist[d].setdefault(s,2)
            # adjlist[s].setdefault(d,1)
        color = {x:0 for x in range(n)}
        print(\"adjlist is {}\".format(adjlist))
        for i in range(1,n):
            if visited[i] == -1:
                dfs(i)
        return doable
        
                        
                    

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [list() for i in range(N)] 
        for dislike in dislikes:
            x = dislike[0]
            y = dislike[1]
            graph[x-1].append(y-1)
            graph[y-1].append(x - 1)
        #print(graph)
        
        
        parent = list(range(N))
        def find(p):
            if p!=parent[p]:
                parent[p] = find(parent[p])
            return parent[p]
        
        def union(p,q):
            pr = find(p)
            qr = find(q)
            if pr!=qr:
                parent[pr] = qr
            return 
        
        for i in range(N):
            if not graph[i]:
                continue
            x = find(i)
            y = find(graph[i][0])
            if x == y:
                return False
            for j in range(1,len(graph[i])):
                z = find(graph[i][j])
                if z == x:
                    return False
                union(y, z)
        
        return True


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)
                       

            

        
        
        


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        edges = {ii: [] for ii in range(1, N + 1)}
        for ii, jj in dislikes:
            edges[ii].append(jj)
            edges[jj].append(ii)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all([dfs(ii, c ^ 1) for ii in edges[node]])
        return all([dfs(ii) for ii in range(1, N + 1) if ii not in color])


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # Solution taken from leetcode solution
        # Insight: I was thinking about the fact that we need to test whether
        # 1 or the other color works for every unvisited node. But, since the
        # graph is an undirected graph, there cannot be an unvisited node that
        # is connected to a visited node once the dfs ends for a connected
        # component
        
        # Process edges into adjacency list
        self.g = collections.defaultdict(list)
        for num1, num2 in dislikes:
            self.g[num1].append(num2)
            self.g[num2].append(num1)
            
            
        self.color = {}
        def dfs(node, c):
            if node in self.color:
                return self.color[node] == c
            else:
                self.color[node] = c
                for dest in self.g[node]:
                    # `1-c` to swap between 0 and 1
                    res = dfs(dest, 1-c)
                    if not res:
                        return False
            return True
        
        for node in self.g:
            if node not in self.color:
                res = dfs(node, 0)
                if not res:
                    return False
                
        return True


from collections import defaultdict
class Solution:
    def possibleBipartition(self, n, dislikes):
        self.visited = {}
        self.graph = defaultdict(list)
        for p1, p2 in dislikes:
            self.graph[p1].append(p2)
            self.graph[p2].append(p1)
        for personId in range(len(self.graph)):
            if personId not in self.visited:
                if not self.dfs(personId, 1): #color the personId 1
                    return False
        return True
        
    def dfs(self, personId, color): #color personId as color. all its dislikers as opposite color. return true if possible. false otherwise
        if personId in self.visited:
            return self.visited[personId]==color

        self.visited[personId] = color
        for neighbor in self.graph[personId]:            
            if not self.dfs(neighbor, -color): #color the neighbor -1*color. opposite to personId
                return False
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N <= 1:
            return True
        
        def paint(node, color):
            if colors[node] != -1:
                return colors[node] != color
            
            colors[node] = color
            
            for adj_node in g[node]:
                if paint(adj_node, (color + 1) % 2):
                    return True
                
            return False
        
        
        g = collections.defaultdict(list)
        
        for a, b in dislikes:
            g[a].append(b)
            g[b].append(a)
            
        colors = dict.fromkeys(g, -1)
            
        for n in g:
            if colors[n] == -1:
                if paint(n, 0):
                    return False
                
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N <= 1:
            return True
        
        def paint(node, color):
            if colors[node] is not None:
                return colors[node] != color
            
            colors[node] = color
            
            new_color = not color
            
            for adj_node in g[node]:
                if paint(adj_node, new_color):
                    return True
                
            return False
        
        
        g = collections.defaultdict(list)
        
        for a, b in dislikes:
            g[a].append(b)
            g[b].append(a)
            
        colors = dict.fromkeys(g, None)
            
        for n in g:
            if colors[n] is None:
                if paint(n, False):
                    return False
                
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        g = collections.defaultdict(list)
        for u, v in dislikes:
            g[u].append(v)
            g[v].append(u)
        
        parent = [i for i in range(N+1)]
        def find(n):
            if n == parent[n]:
                return n
            parent[n] = find(parent[n])
            return parent[n]
        def union(n1, n2):
            r1, r2 = find(n1), find(n2)
            if r1 != r2:
                parent[r1] = r2
        
        for k in g:
            for node in g[k]:
                if find(k) == find(node):
                    return False
                union(g[k][0], node)
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def bfs(n):
            q = [(n, 1)]
            while q:
                x, color = q.pop()
                state[x] = color
                for i in graph[x]:
                    if state[i] == 0: 
                        q.append((i, -color))
                    if state[i] == color: return False
            return True
        
        # build graph
        graph = [set() for _ in range(N+1)]
        for a,b in dislikes: 
            graph[a-1].add(b-1)
            graph[b-1].add(a-1)
        
        state = [0]*N
        for i in range(N):  
            if state[i] != 0: continue
            if not bfs(i): 
                return False        
        return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if len(dislikes) == 0:
            return True
        
        nodeMap = {}
        
        for a, b in dislikes:
            if a not in nodeMap:
                nodeMap[a] = Node(a)
            
            if b not in nodeMap:
                nodeMap[b] = Node(b)
            
            nodeMap[a].connections.append(nodeMap[b])
            nodeMap[b].connections.append(nodeMap[a])
        
        visited = set()
        colored = {}
        
        def dfs(queue: List[Node]) -> bool:
            if len(queue) == 0:
                return True
            
            node = queue.pop()
            #print(node)
            
            if node in visited:
                return dfs(queue)
            
            visited.add(node)
            
            color = 1
            if node in colored:
                color = colored[node]
            
            for connect in node.connections:
                if connect in colored:
                    if colored[connect] == color:
                        return False
                else:
                    colored[connect] = 1 - color
                
                if connect not in visited:
                    queue.append(connect)
            return dfs(queue)
        
        for key,val in list(nodeMap.items()):
            #print(val)
            if val in visited:
                continue
            else:
                res = dfs([val])
                if not res:
                    return False
        return True
            
class Node:
    def __init__(self, val):
        self.val = val
        self.connections = []


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def bfsColoring(g, src, colors):
            queue = [src]
            colors[src] = 0
            
            while queue:
                u = queue.pop(0)
                for v in g[u]:
                    if colors[v] != -1 and colors[v] != 1-colors[u]:
                        return False
                    elif colors[v] == -1:
                        colors[v] = 1-colors[u]
                        queue.append(v)
            print(colors)
            return True
            
        
        g = collections.defaultdict(set)
        
        for dis in dislikes:
            g[dis[0]].add(dis[1])
            g[dis[1]].add(dis[0])
            
        colors = [-1 for _ in range(N+1)]
        for i in range(1, N+1):
            if colors[i] == -1:
                if not bfsColoring(g, i, colors):
                    return False
        print(colors)
        if -1 in set(colors[1:]):
            return False
        return True



class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for i in range(N)]
        for dislike in dislikes:
            graph[dislike[0]-1].append(dislike[1]-1)
            graph[dislike[1]-1].append(dislike[0]-1)
        
        visited = [False for i in range(N)]
        groups = [set([]), set([])]
        def dfs(root, group):
            groups[group].add(root)
            visited[root] = True
            for d in graph[root]:
                if d in groups[group]:
                    return False
                if not visited[d] and not dfs(d, 1 - group):
                    return False
            return True
        
        for i in range(N):
            if not visited[i] and not dfs(i, 0):
                return False
        return True
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)          
        def dfs(graph, color, node, col):
            color[node] = col
            for neigh in graph[node]:
                if color[neigh] == col:
                    return False
                if color[neigh] == 0:
                    if not dfs(graph, color, neigh, -col):
                        return False
            return True     
        color = [0] * (N+1)  
        for i in range(1,N):
            if color[i] == 0:
                if not dfs(graph, color, i, 1):
                    return False
        return True

import queue

def bfs_step(queue, colors, graph, queued):
    node = queue.get()
    color1 = colors[node]
    for edge in graph[node]:
        if colors[edge] == -1:
            colors[edge] = 1 - color1
        if colors[edge] == color1:
            return False
        if not queued[edge]:
            queue.put(edge)
            queued[edge] = 1
    return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        q = queue.SimpleQueue()
        colors = [-1 for i in range(N+1)]
        graph = [[] for i in range(N+1)]
        queued = [0 for i in range(N+1)]
        for edge in dislikes:
            i, j = edge
            graph[i].append(j)
            graph[j].append(i)
        for i in range(N):
            if colors[i] != -1:
                continue
            colors[i] = 1
            if not queued[i]:
                q.put(i)
                queued[i] = 1
            while not q.empty():
                if not bfs_step(q, colors, graph, queued):
                    return False
        return True
                
                
            
        
            


class Solution:
  def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
    # build graph
    graph = collections.defaultdict(list)
    for f, to in dislikes:
      graph[f].append(to)
      graph[to].append(f)
      
    group = collections.defaultdict(bool) # true group and false group
    curr_group = True
    for i in range(1, N+1):
      if i not in group:
        q = collections.deque([i])
        group[i] = curr_group
        while q:
          for _ in range(len(q)):
            node = q.popleft()
            # look at neighbors
            for nei in graph[node]:
              if nei in group and group[nei] == curr_group:
                return False
              elif nei not in group:
                q.append(nei)
                group[nei] = not curr_group
          curr_group = not curr_group
    return True


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(N+1)]
        # print(graph)
        
        for dislike in dislikes:
            # if graph[dislike[0]] == None:
            #     graph[dislike[0]] = []
            # if graph[dislike[1]] == None:
            #     graph[dislike[1]] = []
             
            graph[dislike[0]].append(dislike[1])
            graph[dislike[1]].append(dislike[0])
                
        
        
        
        color = {}
        
        for p in range(N):
            if p in color:
                continue
            color[p] = True
            
            stack = [p]
            while stack:
                p1 = stack.pop()
                for p2 in graph[p1]:
                    if p2 in color:
                        if color[p2] == color[p1]:
                            return False
                    else:
                        color[p2] = not color[p1]
                        stack.append(p2)
                        
        return True
                        
                


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def make_graph(dislikes):
            graph = defaultdict(list)
            for dl in dislikes:
                graph[dl[1]].append(dl[0])
                graph[dl[0]].append(dl[1])
            return graph
        
        graph = make_graph(dislikes)
        visited = {}
        
#         def dfs(node, c=0):
#             if node in color:
#                 return color[node] == c
#             color[node] = c
#             return all(dfs(nei, c^1) for nei in graph[node])
#         return all(dfs(node) for node in range(1, N+1) if node not in color)
    
        for i in range(1, N+1):
            if i in visited:
                continue
            visited[i] = 'red'
            stack = [[i, visited[i]]]
            
         
            while stack:
                num, pos = stack.pop(0)
                for next_num in graph[num]:
                    if next_num in visited:
                        if visited[next_num] == pos:
                      
                            return False
                    else:
                        if pos == 'blue': 
                            next_pos = 'red' 
                        else:
                            next_pos = 'blue' 
                        visited[next_num] = next_pos
                        stack.append([next_num, next_pos])
        return True
                        
                
                    
            
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(p1, color=1):
            colors[color].add(p1)
            for p2 in G[p1]:
                if p2 in colors[color] or (p2 not in colors[-color] and not dfs(p2, -color)):
                    return False
            return True
        G, colors = [[] for _ in range(N)], {-1: set(), 1: set()}
        for p1, p2 in dislikes:
            G[p1-1].append(p2-1)
            G[p2-1].append(p1-1)
        for p in range(N):
            if p not in colors[1] and p not in colors[-1] and not dfs(p):
                return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def make_graph(dislikes):
            graph = defaultdict(list)
            for dl in dislikes:
                graph[dl[1]].append(dl[0])
                graph[dl[0]].append(dl[1])
            return graph
        
        graph = make_graph(dislikes)
        color = {}
        
        def dfs(node, c=0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c^1) for nei in graph[node])
        return all(dfs(node) for node in range(1, N+1) if node not in color)
    
        for i in range(1, N+1):
            if i in visited:
                continue
            visited[i] = 'red'
            stack = [[i, visited[i]]]
            
         
            while stack:
                num, pos = stack.pop(0)
                for next_num in graph[num]:
                    if next_num in visited:
                        if visited[next_num] == pos:
                            print((next_num, num, pos))
                            return False
                    else:
                        if pos == 'blue': 
                            next_pos = 'red' 
                        else:
                            next_pos = 'blue' 
                        visited[next_num] = next_pos
                        stack.append([next_num, next_pos])
        return True
                        
                
                    
            
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        dislikes.sort()
        graph = [[] for _ in range(N+1)]
        
        disjoint = [None for _ in range(N+1)]
        
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        
        self.graph = graph
        self.disjoint = disjoint
        
        for i in range(1, N+1):
            if not self.dfs(i):
                return False
        
        return True
    
    def dfs(self, start, color=None):    
        if self.disjoint[start] is not None:
            return color is None or self.disjoint[start] == color
        
        color = True if color is None else color
        self.disjoint[start] = color
        for other in self.graph[start]:
            if not self.dfs(other, not color):
                return False
        return True
        
                
            
                
            
        
        


class Solution:
    def isbi(self,i,color):
        q=[]
        q.append(i)
        color[i]=1
        while q:
            curr=q.pop(0)
            for j in self.graph[curr]:
                if color[j]==color[curr]:
                    return False
                if color[j]==-1:
                    color[j]=1-color[curr]
                    q.append(j)
        return True
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        self.graph=collections.defaultdict(list)
        for v,u in dislikes:
            self.graph[v].append(u)
            self.graph[u].append(v)
        color=[-1]*(N+1)
        for i in range(1,N+1):
            if color[i]==-1:
                if not self.isbi(i,color):
                    return False
        return True

from collections import defaultdict
class Solution:
    def possibleBipartition(self, N, dislikes):
        G = defaultdict(set)
        for u, v in dislikes:
            G[u].add(v)
            G[v].add(u)
        color = dict()
        def dfs(node, c):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in G[node])
        return all(dfs(node, 0) for node in range(1, N+1) if node not in color)



class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        # build a graph of it
        graph = collections.defaultdict(set)
        for u, v in dislikes: 
            graph[u].add(v)
            graph[v].add(u)
        
        group_map = {}
        def dfs(node, is_one): 
            if node in group_map: 
                return is_one == group_map[node]
            else:
                group_map[node] = is_one
            return all(dfs(nei, not is_one) for nei in graph[node])
            
        return all(dfs(node, True) for node in range(1, N+1) if node not in group_map)
                            
                
                
                
                
            
            
            
        
            
            
            
            
            
                
            
                
            
            
            
            
            
            


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        color = {}
        
        graph = collections.defaultdict(list)
        for pair in dislikes:
            p1, p2 = pair[0], pair[1]
            graph[p1].append(p2)
            graph[p2].append(p1)
        
        def dfs(node):
            for nei in graph[node]:
                if nei in color:
                    if color[nei] == color[node]:
                        return False
                else:
                    color[nei] = 1 - color[node]
                    if not dfs(nei):
                        return False
            return True
        
        for i in range(N):
            if i not in color:
                color[i] = 1
                if not dfs(i):
                    return False
        return True


from collections import deque
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        adj = [[] for i in range(N)]
        
        for a,b in dislikes:
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
            
        color_array = [-1]*N
        
        queue = deque()
        
        for i in range(N):
            if color_array[i]==-1:
                color_array[i] = 1
                queue.append(i)
                while queue:
                    u = queue.popleft()
                    for i in adj[u]:
                        if color_array[i]==-1:
                            color_array[i] = 1-color_array[u]
                            queue.append(i)

                        else:
                            if color_array[u]==color_array[i]:
                                return False
        return True
                


class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def bfs(i):
            stack = []
            color[i] = 0
            stack.append(i)
            while stack:
                cur = stack.pop()
                for nei in dislike_adj[cur]:
                    if color[nei] == color[cur]:
                        return False
                    if color[nei] == -1 and color[nei] != color[cur]:
                        stack.append(nei)
                        color[nei] = 1 - color[cur]
            return True
        
        dislike_adj = collections.defaultdict(list)
        color = {}
        for d in dislikes:
            first = d[0]
            second = d[1]
            dislike_adj[first].append(second)
            dislike_adj[second].append(first)
        for i in range(1, N+1):
            color[i] = color.get(i, -1)
        for i in range(1, N+1):
            if color[i] == -1:
                if not bfs(i):
                    return False
        return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if N == 0:
            return True
        seen = {}
        adj = {i: [] for i in range(N+1) }
        for edge in dislikes: 
            #print('adj  ', adj, 'edge.. ', edge)
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])

      
        def try_marking_all_edges(seen, node, adj, color) -> bool:
            if node in seen:
                return seen[node] == color
            seen[node] = color
            #print(\"try_marking_all_edges()\", node, \"->\", adj[node], \" seen \", seen)
            other_group = color ^ 1
            for a in adj[node]:
                if not try_marking_all_edges(seen, a, adj, other_group):
                    return False
            return True
    
        for node in adj:
            if node not in seen:
                if not try_marking_all_edges(seen, node, adj, 0):
                    return False
            if not try_marking_all_edges(seen, node, adj, seen[node]):
                return False
        return True  

            
            
    def possibleBipartition3(self, N: int, dislikes: List[List[int]]) -> bool:
        if N == 0:
            return True
        seen = {}
        adj = {i: [] for i in range(N+1) }
        for edge in dislikes: 
            ##print('adj  ', adj, 'edge.. ', edge)
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
            
        def try_marking_all_edges(seen, node, adj) -> bool:
            #print(\"try_marking_all_edges()\", node, \"->\", adj[node])
            other_group = 2 if seen[node] == 1 else 1
            for a in adj[node]:
                if a not in seen:
                    seen[a] = other_group
                    continue
                if seen[a] != other_group:
                    return False
            return True
     
        print('adj  ', adj) 
     
        for edge in dislikes:
            print(edge, \"->\", seen)
            if not edge[0] in seen and not edge[1] in seen:
                seen[edge[0]] = 1
                seen[edge[1]] = 2
            elif edge[0] in seen and not edge[1] in seen:
                first_group = seen[edge[0]]
                seen[edge[1]] = 2 if first_group == 1 else 1
            elif edge[1] in seen and not edge[0] in seen:
                first_group = seen[edge[1]]
                seen[edge[0]] = 2 if first_group == 1 else 1
            else:
                if seen[edge[0]] == seen[edge[1]]:
                    return False
            if not try_marking_all_edges(seen, edge[0], adj): 
                return False
            if not try_marking_all_edges(seen, edge[1], adj):
                return False
            #print(edge, \"->>> \", seen)   


        return True    
            
            
        
    
    def possibleBipartition2(self, N: int, dislikes: List[List[int]]) -> bool:
        if N == 0:
            return True
        seen = {}
        for edge in dislikes: 
            if not edge[0] in seen and not edge[1] in seen:
                seen[edge[0]] = 1
                seen[edge[1]] = 2
            elif edge[0] in seen and not edge[1] in seen:
                first_group = seen[edge[0]]
                seen[edge[1]] = 2 if first_group == 1 else 1
            elif edge[1] in seen and not edge[0] in seen:
                first_group = seen[edge[1]]
                seen[edge[0]] = 2 if first_group == 1 else 1
            else:
                if seen[edge[0]] == seen[edge[1]]:
                    return False
        return True
                
            
        
        

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        from collections import defaultdict
        def build_graph():
            graph = defaultdict(set)
            for u, v in dislikes:
                graph[u].add(v)
                graph[v].add(u)
            return graph
        
        
        def dfs(node, next_color):
            if node in color: return color[node] == next_color
            color[node] = next_color
            for nei in graph[node]:
                if not dfs(nei, next_color^1):
                    return False
            return True
            
        graph = build_graph()
        color = {}
        for node in graph:
            if node not in color:
                if not dfs(node, 0): return False
        return True

class Solution:

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

        graph = {i: set() for i in range(1, N + 1)}
        for u, v in dislikes:
            graph[u].add(v)
            graph[v].add(u)

        colours = {}

        for u in graph:
            colours.setdefault(u, False)

            st = [u]
            while st:
                a = st.pop()
                ca = colours[a]

                for v in graph[a]:
                    cv = colours.get(v)
                    if cv is not None:
                        if cv == ca:
                            return False
                    else:
                        colours[v] = not ca
                        st.append(v)
        return True

def dfs(adjList, visited, node):
    teams = {node: 1}
    visited.add(node)
    stack = [node]
    while stack:
        node = stack.pop()
        team = teams[node]
        for adjNode in adjList[node]:
            if adjNode in teams and teams[adjNode] == team:
                return False
            if adjNode not in teams:
                teams[adjNode] = 1 - team
                visited.add(adjNode)
                stack.append(adjNode)
    return True

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        adjList = {i: [] for i in range(1, N + 1)}
        for dislike in dislikes:
            x = dislike[0]
            y = dislike[1]
            adjList[x].append(y)
            adjList[y].append(x)
            
        visited = set()
        for i in range(1, N + 1):
            if i not in visited:
                if not dfs(adjList, visited, i):
                    return False
        return True