






"""simple docstring"""




# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
from queue import Queue





def 						__UpperCAmelCase      (					a_):
							snake_case_           =							Queue()
							snake_case_           =							[False] * len(a_)
							snake_case_           =							[-1] * len(a_)

							def bfs():
														while not queue.empty():
																					snake_case_           =							queue.get()
																					snake_case_           =							True

																					for neighbour in graph[u]:
																												if neighbour == u:
																																			return False

																												if color[neighbour] == -1:
																																			snake_case_           =							1 - color[u]
																																			queue.put(a_)

																												elif color[neighbour] == color[u]:
																																			return False

														return True

							for i in range(len(a_)):
														if not visited[i]:
																					queue.put(a_)
																					snake_case_           =							0
																					if bfs() is False:
																												return False

							return True


if __name__ == "__main__":
	# Adjacency List of graph
	print(check_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))













def 						__UpperCAmelCase      (					a_):
							return 1 if input_a == 0 else 0





def 						__UpperCAmelCase      (					):
							assert not_gate(0) == 1
							assert not_gate(1) == 0


if __name__ == "__main__":
	print(not_gate(0))
	print(not_gate(1))





