
# 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 				__magic_name__				(     __lowerCAmelCase			:		Optional[int]							)    ->     Union[str, Any]:
				__lowerCamelCase					      =			Queue()
				__lowerCamelCase					      =			[False] * len(__lowerCAmelCase							)
				__lowerCamelCase					      =			[-1] * len(__lowerCAmelCase							)

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

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

																if color[neighbour] == -1:
																				__lowerCamelCase					      =			1 - color[u]
																				queue.put(__lowerCAmelCase							)

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

								return True

				for i in range(len(__lowerCAmelCase							)							):
								if not visited[i]:
												queue.put(__lowerCAmelCase							)
												__lowerCamelCase					      =			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 				__magic_name__				(     __lowerCAmelCase			:		list	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int							)    ->     int:
				__lowerCamelCase					      =			int((lower_bound + upper_bound) // 2							)
				if array[r] == value:
								return r
				if lower_bound >= upper_bound:
								return -1
				if array[r] < value:
								return binary_search(__lowerCAmelCase	,						r + 1	,						__lowerCAmelCase	,						__lowerCAmelCase							)
				else:
								return binary_search(__lowerCAmelCase	,						__lowerCAmelCase	,						r - 1	,						__lowerCAmelCase							)




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		list							)    ->     list:
				__lowerCamelCase					      =			0
				if matrix[index][0] == value:
								return [index, 0]
				while index < len(__lowerCAmelCase							) and matrix[index][0] < value:
								__lowerCamelCase					      =			binary_search(matrix[index]	,						0	,						len(matrix[index]							) - 1	,						__lowerCAmelCase							)
								if r != -1:
												return [index, r]
								index += 1
				return [-1, -1]


if __name__ == "__main__":
					import doctest

					doctest.testmod()



