
"""simple docstring"""




from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


a_            =   {'configuration_nat': ['NAT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'NatConfig']}


try:
			if not is_torch_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			a_            =   [
			    'NAT_PRETRAINED_MODEL_ARCHIVE_LIST',
			    'NatForImageClassification',
			    'NatModel',
			    'NatPreTrainedModel',
			    'NatBackbone',
			]

if TYPE_CHECKING:
			from .configuration_nat import NAT_PRETRAINED_CONFIG_ARCHIVE_MAP, NatConfig

			try:
						if not is_torch_available():
									raise OptionalDependencyNotAvailable()
			except OptionalDependencyNotAvailable:
						pass
			else:
						from .modeling_nat import (
						    NAT_PRETRAINED_MODEL_ARCHIVE_LIST,
						    NatBackbone,
						    NatForImageClassification,
						    NatModel,
						    NatPreTrainedModel,
						)

else:
			import sys

			a_            =   _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)









"""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      (				__UpperCamelCase					):
			__lowercase	:       int				=   Queue()
			__lowercase	:       str				=   [False] * len(__UpperCamelCase					)
			__lowercase	:       str				=   [-1] * len(__UpperCamelCase					)

			def bfs():
						while not queue.empty():
									__lowercase	:       int				=   queue.get()
									__lowercase	:       List[str]				=   True

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

												if color[neighbour] == -1:
															__lowercase	:       str				=   1 - color[u]
															queue.put(__UpperCamelCase					)

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

						return True

			for i in range(len(__UpperCamelCase					)					):
						if not visited[i]:
									queue.put(__UpperCamelCase					)
									__lowercase	:       int				=   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]}))



