






'''simple docstring'''







import unittest

from transformers.utils.backbone_utils import (
    BackboneMixin,
    get_aligned_output_features_output_indices,
    verify_out_features_out_indices,
)

class _lowercase			(       unittest.TestCase	):




       def 	lowerCamelCase_       (							self:       List[Any]  ):
              lowerCamelCase__      :			str 						= ["""a""", """b""", """c"""]

              # Defaults to last layer if both are None
              lowerCamelCase__      :			Tuple 						= get_aligned_output_features_output_indices(UpperCamelCase__    ,							UpperCamelCase__    ,							UpperCamelCase__  )
              self.assertEqual(UpperCamelCase__    ,							["""c"""]  )
              self.assertEqual(UpperCamelCase__    ,							[2]  )

              # Out indices set to match out features
              lowerCamelCase__      :			Any 						= get_aligned_output_features_output_indices(["""a""", """c"""]    ,							UpperCamelCase__    ,							UpperCamelCase__  )
              self.assertEqual(UpperCamelCase__    ,							["""a""", """c"""]  )
              self.assertEqual(UpperCamelCase__    ,							[0, 2]  )

              # Out features set to match out indices
              lowerCamelCase__      :			Dict 						= get_aligned_output_features_output_indices(UpperCamelCase__    ,							[0, 2]    ,							UpperCamelCase__  )
              self.assertEqual(UpperCamelCase__    ,							["""a""", """c"""]  )
              self.assertEqual(UpperCamelCase__    ,							[0, 2]  )

              # Out features selected from negative indices
              lowerCamelCase__      :			List[str] 						= get_aligned_output_features_output_indices(UpperCamelCase__    ,							[-3, -1]    ,							UpperCamelCase__  )
              self.assertEqual(UpperCamelCase__    ,							["""a""", """c"""]  )
              self.assertEqual(UpperCamelCase__    ,							[-3, -1]  )




       def 	lowerCamelCase_       (							self:       List[Any]  ):
              # Stage names must be set
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(["""a""", """b"""]    ,							(0, 1)    ,							UpperCamelCase__  )

              # Out features must be a list
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(("""a""", """b""")    ,							(0, 1)    ,							["""a""", """b"""]  )

              # Out features must be a subset of stage names
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(["""a""", """b"""]    ,							(0, 1)    ,							["""a"""]  )

              # Out indices must be a list or tuple
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(UpperCamelCase__    ,							0    ,							["""a""", """b"""]  )

              # Out indices must be a subset of stage names
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(UpperCamelCase__    ,							(0, 1)    ,							["""a"""]  )

              # Out features and out indices must be the same length
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(["""a""", """b"""]    ,							(0,)    ,							["""a""", """b""", """c"""]  )

              # Out features should match out indices
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(["""a""", """b"""]    ,							(0, 2)    ,							["""a""", """b""", """c"""]  )

              # Out features and out indices should be in order
              with self.assertRaises(UpperCamelCase__  ):
                     verify_out_features_out_indices(["""b""", """a"""]    ,							(0, 1)    ,							["""a""", """b"""]  )

              # Check passes with valid inputs
              verify_out_features_out_indices(["""a""", """b""", """d"""]    ,							(0, 1, -1)    ,							["""a""", """b""", """c""", """d"""]  )




       def 	lowerCamelCase_       (							self:       Union[str, Any]  ):
              lowerCamelCase__      :			str 						= BackboneMixin()

              lowerCamelCase__      :			Optional[Any] 						= ["""a""", """b""", """c"""]
              lowerCamelCase__      :			List[str] 						= ["""a""", """c"""]
              lowerCamelCase__      :			Any 						= [0, 2]

              # Check that the output features and indices are set correctly
              self.assertEqual(backbone.out_features    ,							["""a""", """c"""]  )
              self.assertEqual(backbone.out_indices    ,							[0, 2]  )

              # Check out features and indices are updated correctly
              lowerCamelCase__      :			Optional[Any] 						= ["""a""", """b"""]
              self.assertEqual(backbone.out_features    ,							["""a""", """b"""]  )
              self.assertEqual(backbone.out_indices    ,							[0, 1]  )

              lowerCamelCase__      :			str 						= [-3, -1]
              self.assertEqual(backbone.out_features    ,							["""a""", """c"""]  )
              self.assertEqual(backbone.out_indices    ,							[-3, -1]  )









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





def 				SCREAMING_SNAKE_CASE_ (UpperCamelCase   )   -> Optional[Any]:
							lowerCamelCase__      :			str 						= [False] * len(UpperCamelCase   )
							lowerCamelCase__      :			str 						= [-1] * len(UpperCamelCase   )

							def dfs(UpperCamelCase       ,    UpperCamelCase   ):
														lowerCamelCase__      :			Optional[int] 						= True
														lowerCamelCase__      :			Union[str, Any] 						= c
														for u in graph[v]:
																					if not visited[u]:
																												dfs(UpperCamelCase       ,    1 - c   )

							for i in range(len(UpperCamelCase   )   ):
														if not visited[i]:
																					dfs(UpperCamelCase       ,    0   )

							for i in range(len(UpperCamelCase   )   ):
														for j in graph[i]:
																					if color[i] == color[j]:
																												return False

							return True


# Adjacency list of graph
_A			:    int					  ={0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}



print(check_bipartite_dfs(graph))

