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].

Source: leetcode | Difficulty: MEDIUM
Tags: Spanning trees

Graph algorithms

Graph traversal

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
		return True

	def dfs(self, idx, color, graph, 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
			elif 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:

	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)
		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
				elif 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:
		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:

	def create_adjacency_list(self, dislikes):
		adjacency_list = defaultdict(list)
		for (i, j) in dislikes:
			adjacency_list[i].append(j)
			adjacency_list[j].append(i)
		return adjacency_list

	def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
		adjacency_list = self.create_adjacency_list(dislikes)
		print(adjacency_list)
		color = {vertex: -1 for vertex in adjacency_list}
		print(color)
		queue = deque()
		for vertex in adjacency_list:
			if color[vertex] == -1:
				color[vertex] = 0
				queue.append(vertex)
				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:
							color[neighbor] = 1 - color[current_node]
							queue.append(neighbor)
		return True


from collections import defaultdict

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


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:
		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 person in range(1, N + 1):
			if person not in visited:
				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 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


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:

	def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
		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]:
				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:
			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


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:
		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:

	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)
		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]:
							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]
							elif color[nei] != 1 - color[node]:
								return False
						size -= 1
		return len(set(color)) == 3


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)

		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)
					elif visited[nei] == clr:
						return False
		return True


import collections

class Solution:

	def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
		graph = collections.defaultdict(list)
		for (fr, to) in dislikes:
			graph[fr].append(to)
			graph[to].append(fr)
		group = collections.defaultdict(bool)
		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()
						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


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


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:
		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: 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:
			group1[group1Person] += 1
			group2[group2Person] += 1
			if index == len(dislikes):
				return True
			(a, b) = dislikes[index]
			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)


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)
				elif 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:
		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


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]
						elif group[i] != 1 - group[ele]:
							return False
		return True


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)
			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] != []])


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))


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 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
					elif 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


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


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:

		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))
			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:
						uf.union(i - 1, j - 1)
			return len(set(uf.p)) == 2

		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:
		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 = {}

		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))


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)
		colors = [0 for i in range(N)]
		for i in range(N):
			if colors[i] != 0:
				continue
			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
		graph = {i: [] for i in range(1, N + 1)}
		for (a, b) in dislikes:
			graph[a].append(b)
			graph[b].append(a)
		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:
		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:
				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)
		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
				elif 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 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]
				L1 = r2.copy()
				L2 = set()
				while 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()
		return True


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)
		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:

	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:
		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]:
					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):
					return False
		return True

	def dfs(self, personId, color):
		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):
				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
		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()
			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()):
			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 = 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:
		graph = [[] for _ in range(N + 1)]
		for dislike in dislikes:
			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:

	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 = {}
		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:
		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)
						elif 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:
		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