
import gc
import unittest

from transformers import MODEL_FOR_MASKED_LM_MAPPING, TF_MODEL_FOR_MASKED_LM_MAPPING, FillMaskPipeline, pipeline
from transformers.pipelines import PipelineException
from transformers.testing_utils import (
    is_pipeline_test,
    is_torch_available,
    nested_simplify,
    require_tf,
    require_torch,
    require_torch_gpu,
    slow,
)

from .test_pipelines_common import ANY


@is_pipeline_test
class   __lowerCAmelCase		(		unittest.TestCase					):



      """simple docstring"""







      A__		:	str         =			MODEL_FOR_MASKED_LM_MAPPING
      A__		:	Optional[int]         =			TF_MODEL_FOR_MASKED_LM_MAPPING




      def 						snake_case_	(					self						:				Any ):
          super().tearDown()
          # clean-up as much as possible GPU memory occupied by PyTorch
          gc.collect()
          if is_torch_available():
              import torch

              torch.cuda.empty_cache()




      @require_tf
      def 						snake_case_	(					self						:				Optional[int] ):
          __lowercase						:	Optional[Any]					=				pipeline(task='''fill-mask''' ,				model='''sshleifer/tiny-distilroberta-base''' ,				top_k=2 ,				framework='''tf''' )
          __lowercase						:	Any					=				unmasker('''My name is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {'''sequence''': '''My name is grouped''', '''score''': 2.1E-0_5, '''token''': 3_8015, '''token_str''': ''' grouped'''},
                  {'''sequence''': '''My name is accuser''', '''score''': 2.1E-0_5, '''token''': 2_5506, '''token_str''': ''' accuser'''},
              ] ,				)

          __lowercase						:	Any					=				unmasker('''The largest city in France is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {
                      '''sequence''': '''The largest city in France is grouped''',
                      '''score''': 2.1E-0_5,
                      '''token''': 3_8015,
                      '''token_str''': ''' grouped''',
                  },
                  {
                      '''sequence''': '''The largest city in France is accuser''',
                      '''score''': 2.1E-0_5,
                      '''token''': 2_5506,
                      '''token_str''': ''' accuser''',
                  },
              ] ,				)

          __lowercase						:	Union[str, Any]					=				unmasker('''My name is <mask>''' ,				targets=[''' Patrick''', ''' Clara''', ''' Teven'''] ,				top_k=3 )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {'''sequence''': '''My name is Clara''', '''score''': 2E-0_5, '''token''': 1_3606, '''token_str''': ''' Clara'''},
                  {'''sequence''': '''My name is Patrick''', '''score''': 2E-0_5, '''token''': 3499, '''token_str''': ''' Patrick'''},
                  {'''sequence''': '''My name is Te''', '''score''': 1.9E-0_5, '''token''': 2941, '''token_str''': ''' Te'''},
              ] ,				)




      @require_torch
      def 						snake_case_	(					self						:				str ):
          __lowercase						:	Union[str, Any]					=				pipeline(task='''fill-mask''' ,				model='''sshleifer/tiny-distilroberta-base''' ,				top_k=2 ,				framework='''pt''' )

          __lowercase						:	Any					=				unmasker('''My name is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {'''sequence''': '''My name is Maul''', '''score''': 2.2E-0_5, '''token''': 3_5676, '''token_str''': ''' Maul'''},
                  {'''sequence''': '''My name isELS''', '''score''': 2.2E-0_5, '''token''': 1_6416, '''token_str''': '''ELS'''},
              ] ,				)

          __lowercase						:	Any					=				unmasker('''The largest city in France is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {
                      '''sequence''': '''The largest city in France is Maul''',
                      '''score''': 2.2E-0_5,
                      '''token''': 3_5676,
                      '''token_str''': ''' Maul''',
                  },
                  {'''sequence''': '''The largest city in France isELS''', '''score''': 2.2E-0_5, '''token''': 1_6416, '''token_str''': '''ELS'''},
              ] ,				)

          __lowercase						:	Union[str, Any]					=				unmasker('''My name is <mask>''' ,				targets=[''' Patrick''', ''' Clara''', ''' Teven'''] ,				top_k=3 )
          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  {'''sequence''': '''My name is Patrick''', '''score''': 2.1E-0_5, '''token''': 3499, '''token_str''': ''' Patrick'''},
                  {'''sequence''': '''My name is Te''', '''score''': 2E-0_5, '''token''': 2941, '''token_str''': ''' Te'''},
                  {'''sequence''': '''My name is Clara''', '''score''': 2E-0_5, '''token''': 1_3606, '''token_str''': ''' Clara'''},
              ] ,				)

          __lowercase						:	List[str]					=				unmasker('''My name is <mask> <mask>''' ,				top_k=2 )

          self.assertEqual(
              nested_simplify(__snake_case ,				decimals=6 ) ,				[
                  [
                      {
                          '''score''': 2.2E-0_5,
                          '''token''': 3_5676,
                          '''token_str''': ''' Maul''',
                          '''sequence''': '''<s>My name is Maul<mask></s>''',
                      },
                      {'''score''': 2.2E-0_5, '''token''': 1_6416, '''token_str''': '''ELS''', '''sequence''': '''<s>My name isELS<mask></s>'''},
                  ],
                  [
                      {
                          '''score''': 2.2E-0_5,
                          '''token''': 3_5676,
                          '''token_str''': ''' Maul''',
                          '''sequence''': '''<s>My name is<mask> Maul</s>''',
                      },
                      {'''score''': 2.2E-0_5, '''token''': 1_6416, '''token_str''': '''ELS''', '''sequence''': '''<s>My name is<mask>ELS</s>'''},
                  ],
              ] ,				)




      @require_torch_gpu
      def 						snake_case_	(					self						:				Optional[Any] ):
          __lowercase						:	int					=				pipeline('''fill-mask''' ,				model='''hf-internal-testing/tiny-random-distilbert''' ,				device=0 ,				framework='''pt''' )

          # convert model to fp16
          pipe.model.half()

          __lowercase						:	Dict					=				pipe('''Paris is the [MASK] of France.''' )
          # We actually don't care about the result, we just want to make sure
          # it works, meaning the float16 tensor got casted back to float32
          # for postprocessing.
          self.assertIsInstance(__snake_case ,				__snake_case )




      @slow
      @require_torch
      def 						snake_case_	(					self						:				List[str] ):
          __lowercase						:	str					=				pipeline(task='''fill-mask''' ,				model='''distilroberta-base''' ,				top_k=2 ,				framework='''pt''' )
          self.run_large_test(__snake_case )




      @slow
      @require_tf
      def 						snake_case_	(					self						:				str ):
          __lowercase						:	int					=				pipeline(task='''fill-mask''' ,				model='''distilroberta-base''' ,				top_k=2 ,				framework='''tf''' )
          self.run_large_test(__snake_case )




      def 						snake_case_	(					self						:				Optional[Any] ,				_snake_case						:				Any ):
          __lowercase						:	Any					=				unmasker('''My name is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ) ,				[
                  {'''sequence''': '''My name is John''', '''score''': 0.0_08, '''token''': 610, '''token_str''': ''' John'''},
                  {'''sequence''': '''My name is Chris''', '''score''': 0.0_07, '''token''': 1573, '''token_str''': ''' Chris'''},
              ] ,				)
          __lowercase						:	Optional[int]					=				unmasker('''The largest city in France is <mask>''' )
          self.assertEqual(
              nested_simplify(__snake_case ) ,				[
                  {
                      '''sequence''': '''The largest city in France is Paris''',
                      '''score''': 0.2_51,
                      '''token''': 2201,
                      '''token_str''': ''' Paris''',
                  },
                  {
                      '''sequence''': '''The largest city in France is Lyon''',
                      '''score''': 0.2_14,
                      '''token''': 1_2790,
                      '''token_str''': ''' Lyon''',
                  },
              ] ,				)

          __lowercase						:	int					=				unmasker('''My name is <mask>''' ,				targets=[''' Patrick''', ''' Clara''', ''' Teven'''] ,				top_k=3 )
          self.assertEqual(
              nested_simplify(__snake_case ) ,				[
                  {'''sequence''': '''My name is Patrick''', '''score''': 0.0_05, '''token''': 3499, '''token_str''': ''' Patrick'''},
                  {'''sequence''': '''My name is Clara''', '''score''': 0.0_00, '''token''': 1_3606, '''token_str''': ''' Clara'''},
                  {'''sequence''': '''My name is Te''', '''score''': 0.0_00, '''token''': 2941, '''token_str''': ''' Te'''},
              ] ,				)




      @require_torch
      def 						snake_case_	(					self						:				Optional[Any] ):
          __lowercase						:	Union[str, Any]					=				pipeline(task='''fill-mask''' ,				model='''sshleifer/tiny-distilroberta-base''' ,				framework='''pt''' )
          __lowercase						:	str					=				None
          __lowercase						:	Optional[int]					=				None
          self.run_pipeline_test(__snake_case ,				[] )




      @require_tf
      def 						snake_case_	(					self						:				Optional[Any] ):
          __lowercase						:	List[str]					=				pipeline(task='''fill-mask''' ,				model='''sshleifer/tiny-distilroberta-base''' ,				framework='''tf''' )
          __lowercase						:	Tuple					=				None
          __lowercase						:	Union[str, Any]					=				None
          self.run_pipeline_test(__snake_case ,				[] )




      def 						snake_case_	(					self						:				Any ,				_snake_case						:				Tuple ,				_snake_case						:				Optional[Any] ,				_snake_case						:				List[Any] ):
          if tokenizer is None or tokenizer.mask_token_id is None:
              self.skipTest('''The provided tokenizer has no mask token, (probably reformer or wav2vec2)''' )

          __lowercase						:	Union[str, Any]					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )
          __lowercase						:	List[str]					=				[
              F'This is another {tokenizer.mask_token} test',
          ]
          return fill_masker, examples




      def 						snake_case_	(					self						:				Tuple ,				_snake_case						:				Tuple ,				_snake_case						:				str ):
          __lowercase						:	Union[str, Any]					=				fill_masker.tokenizer
          __lowercase						:	Dict					=				fill_masker.model

          __lowercase						:	Optional[int]					=				fill_masker(
              F'This is a {tokenizer.mask_token}' ,				)
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)

          __lowercase						:	List[str]					=				fill_masker([F'This is a {tokenizer.mask_token}'] )
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)

          __lowercase						:	Any					=				fill_masker([F'This is a {tokenizer.mask_token}', F'Another {tokenizer.mask_token} great test.'] )
          self.assertEqual(
              __snake_case ,				[
                  [
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  ],
                  [
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  ],
              ] ,				)

          with self.assertRaises(__snake_case ):
              fill_masker([None] )
          # No mask_token is not supported
          with self.assertRaises(__snake_case ):
              fill_masker('''This is''' )

          self.run_test_top_k(__snake_case ,				__snake_case )
          self.run_test_targets(__snake_case ,				__snake_case )
          self.run_test_top_k_targets(__snake_case ,				__snake_case )
          self.fill_mask_with_duplicate_targets_and_top_k(__snake_case ,				__snake_case )
          self.fill_mask_with_multiple_masks(__snake_case ,				__snake_case )




      def 						snake_case_	(					self						:				Union[str, Any] ,				_snake_case						:				Optional[int] ,				_snake_case						:				Dict ):
          __lowercase						:	Optional[int]					=				tokenizer.get_vocab()
          __lowercase						:	int					=				sorted(vocab.keys() )[:2]
          # Pipeline argument
          __lowercase						:	int					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case ,				targets=__snake_case )
          __lowercase						:	List[Any]					=				fill_masker(F'This is a {tokenizer.mask_token}' )
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)
          __lowercase						:	Optional[int]					=				{vocab[el] for el in targets}
          self.assertEqual({el['''token'''] for el in outputs} ,				__snake_case )
          __lowercase						:	Optional[Any]					=				[tokenizer.decode([x] ) for x in target_ids]
          self.assertEqual({el['''token_str'''] for el in outputs} ,				set(__snake_case ) )

          # Call argument
          __lowercase						:	List[str]					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )
          __lowercase						:	str					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets=__snake_case )
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)
          __lowercase						:	Optional[Any]					=				{vocab[el] for el in targets}
          self.assertEqual({el['''token'''] for el in outputs} ,				__snake_case )
          __lowercase						:	Union[str, Any]					=				[tokenizer.decode([x] ) for x in target_ids]
          self.assertEqual({el['''token_str'''] for el in outputs} ,				set(__snake_case ) )

          # Score equivalence
          __lowercase						:	List[str]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets=__snake_case )
          __lowercase						:	Tuple					=				[top_mask['''token_str'''] for top_mask in outputs]
          __lowercase						:	int					=				[top_mask['''score'''] for top_mask in outputs]

          # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
          if set(__snake_case ) == set(__snake_case ):
              __lowercase						:	Dict					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets=__snake_case )
              __lowercase						:	int					=				[top_mask['''score'''] for top_mask in unmasked_targets]
              self.assertEqual(nested_simplify(__snake_case ) ,				nested_simplify(__snake_case ) )

          # Raises with invalid
          with self.assertRaises(__snake_case ):
              __lowercase						:	Optional[int]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets=[] )
          # For some tokenizers, `""` is actually in the vocabulary and the expected error won't raised
          if "" not in tokenizer.get_vocab():
              with self.assertRaises(__snake_case ):
                  __lowercase						:	Optional[int]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets=[''''''] )
              with self.assertRaises(__snake_case ):
                  __lowercase						:	Optional[int]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				targets='''''' )




      def 						snake_case_	(					self						:				int ,				_snake_case						:				str ,				_snake_case						:				Union[str, Any] ):
          __lowercase						:	Union[str, Any]					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case ,				top_k=2 )
          __lowercase						:	Tuple					=				fill_masker(F'This is a {tokenizer.mask_token}' )
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)

          __lowercase						:	List[Any]					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )
          __lowercase						:	Union[str, Any]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				top_k=2 )
          self.assertEqual(
              __snake_case ,				[
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
              ] ,				)
          self.assertEqual(nested_simplify(__snake_case ) ,				nested_simplify(__snake_case ) )




      def 						snake_case_	(					self						:				Optional[int] ,				_snake_case						:				List[Any] ,				_snake_case						:				Tuple ):
          __lowercase						:	List[Any]					=				tokenizer.get_vocab()
          __lowercase						:	int					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )

          # top_k=2, ntargets=3
          __lowercase						:	Any					=				sorted(vocab.keys() )[:3]
          __lowercase						:	str					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				top_k=2 ,				targets=__snake_case )

          # If we use the most probably targets, and filter differently, we should still
          # have the same results
          __lowercase						:	int					=				[el['''token_str'''] for el in sorted(__snake_case ,				key=lambda _snake_case : x["score"] ,				reverse=__snake_case )]
          # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
          if set(__snake_case ).issubset(__snake_case ):
              __lowercase						:	Optional[Any]					=				fill_masker(F'This is a {tokenizer.mask_token}' ,				top_k=3 ,				targets=__snake_case )
              # They should yield exactly the same result
              self.assertEqual(nested_simplify(__snake_case ) ,				nested_simplify(__snake_case ) )




      def 						snake_case_	(					self						:				Tuple ,				_snake_case						:				List[str] ,				_snake_case						:				Optional[Any] ):
          __lowercase						:	Optional[Any]					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )
          __lowercase						:	Optional[Any]					=				tokenizer.get_vocab()
          # String duplicates + id duplicates
          __lowercase						:	List[Any]					=				sorted(vocab.keys() )[:3]
          __lowercase						:	Tuple					=				[targets[0], targets[1], targets[0], targets[2], targets[1]]
          __lowercase						:	Union[str, Any]					=				fill_masker(F'My name is {tokenizer.mask_token}' ,				targets=__snake_case ,				top_k=10 )

          # The target list contains duplicates, so we can't output more
          # than them
          self.assertEqual(len(__snake_case ) ,				3 )




      def 						snake_case_	(					self						:				Optional[int] ,				_snake_case						:				Optional[int] ,				_snake_case						:				List[Any] ):
          __lowercase						:	Dict					=				FillMaskPipeline(model=__snake_case ,				tokenizer=__snake_case )

          __lowercase						:	int					=				fill_masker(
              F'This is a {tokenizer.mask_token} {tokenizer.mask_token} {tokenizer.mask_token}' ,				top_k=2 )
          self.assertEqual(
              __snake_case ,				[
                  [
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  ],
                  [
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  ],
                  [
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                      {'''sequence''': ANY(__snake_case ), '''score''': ANY(__snake_case ), '''token''': ANY(__snake_case ), '''token_str''': ANY(__snake_case )},
                  ],
              ] ,				)





# 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        UpperCamelCase_(							_snake_case   :  Tuple	):




			"""simple docstring"""






			__a        =[False] * len(_snake_case	)
			__a        =[-1] * len(_snake_case	)

			def dfs(_snake_case   :  Dict       ,     _snake_case   :  Any	):
						__a        =True
						__a        =c
						for u in graph[v]:
									if not visited[u]:
												dfs(_snake_case       ,     1 - c	)

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

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

			return True


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


print(check_bipartite_dfs(graph))






