






import inspect
import unittest

import numpy as np

from tests.test_modeling_common import floats_tensor
from transformers import DetrConfig, MaskFormerConfig, SwinConfig, is_torch_available, is_vision_available
from transformers.testing_utils import require_torch, require_torch_multi_gpu, require_vision, slow, torch_device
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
   import torch

   from transformers import MaskFormerForInstanceSegmentation, MaskFormerModel

   if is_vision_available():
      from transformers import MaskFormerImageProcessor

if is_vision_available():
   from PIL import Image




class     _lowerCAmelCase:





       """simple docstring"""







       def __init__( self  ,      _lowerCamelCase  ,      _lowerCamelCase=2  ,      _lowerCamelCase=True  ,      _lowerCamelCase=False  ,      _lowerCamelCase=1_0  ,      _lowerCamelCase=3  ,      _lowerCamelCase=3_2 * 4  ,      _lowerCamelCase=3_2 * 6  ,      _lowerCamelCase=4  ,      _lowerCamelCase=3_2  ,      ):
         UpperCamelCase_: str   				=    parent
         UpperCamelCase_: Tuple   				=    batch_size
         UpperCamelCase_: str   				=    is_training
         UpperCamelCase_: Optional[int]   				=    use_auxiliary_loss
         UpperCamelCase_: List[str]   				=    num_queries
         UpperCamelCase_: Dict   				=    num_channels
         UpperCamelCase_: Tuple   				=    min_size
         UpperCamelCase_: Optional[int]   				=    max_size
         UpperCamelCase_: Optional[Any]   				=    num_labels
         UpperCamelCase_: Optional[int]   				=    mask_feature_size





       def       _a   ( self							):
         UpperCamelCase_: Dict   				=    floats_tensor([self.batch_size, self.num_channels, self.min_size, self.max_size]							).to(
             _lowerCamelCase							)

         UpperCamelCase_: List[str]   				=    torch.ones([self.batch_size, self.min_size, self.max_size]  ,      device=_lowerCamelCase							)

         UpperCamelCase_: Union[str, Any]   				=    (
             torch.rand([self.batch_size, self.num_labels, self.min_size, self.max_size]  ,      device=_lowerCamelCase							) > 0.5
         ).float()
         UpperCamelCase_: int   				=    (torch.rand((self.batch_size, self.num_labels)  ,      device=_lowerCamelCase							) > 0.5).long()

         UpperCamelCase_: Any   				=    self.get_config()
         return config, pixel_values, pixel_mask, mask_labels, class_labels





       def       _a   ( self							):
         return MaskFormerConfig.from_backbone_and_decoder_configs(
             backbone_config=SwinConfig(
                 depths=[1, 1, 1, 1]  ,      )  ,      decoder_config=DetrConfig(
                 decoder_ffn_dim=1_2_8  ,      num_queries=self.num_queries  ,      decoder_attention_heads=2  ,      d_model=self.mask_feature_size  ,      )  ,      mask_feature_size=self.mask_feature_size  ,      fpn_feature_size=self.mask_feature_size  ,      num_channels=self.num_channels  ,      num_labels=self.num_labels  ,      )





       def       _a   ( self							):
         UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_: str   				=    self.prepare_config_and_inputs()
         UpperCamelCase_: List[Any]   				=    {'pixel_values': pixel_values, 'pixel_mask': pixel_mask}
         return config, inputs_dict





       def       _a   ( self  ,      _lowerCamelCase  ,      _lowerCamelCase							):
         UpperCamelCase_: Any   				=    output.encoder_hidden_states
         UpperCamelCase_: Any   				=    output.pixel_decoder_hidden_states
         UpperCamelCase_: Dict   				=    output.transformer_decoder_hidden_states

         self.parent.assertTrue(len(_lowerCamelCase							)  ,      len(config.backbone_config.depths							)							)
         self.parent.assertTrue(len(_lowerCamelCase							)  ,      len(config.backbone_config.depths							)							)
         self.parent.assertTrue(len(_lowerCamelCase							)  ,      config.decoder_config.decoder_layers							)





       def       _a   ( self  ,      _lowerCamelCase  ,      _lowerCamelCase  ,      _lowerCamelCase  ,      _lowerCamelCase=False							):
         with torch.no_grad():
           UpperCamelCase_: Optional[Any]   				=    MaskFormerModel(config=_lowerCamelCase							)
           model.to(_lowerCamelCase							)
           model.eval()

           UpperCamelCase_: str   				=    model(pixel_values=_lowerCamelCase  ,      pixel_mask=_lowerCamelCase							)
           UpperCamelCase_: Dict   				=    model(_lowerCamelCase  ,      output_hidden_states=_lowerCamelCase							)
         # the correct shape of output.transformer_decoder_hidden_states ensure the correcteness of the
         # encoder and pixel decoder
         self.parent.assertEqual(
             output.transformer_decoder_last_hidden_state.shape  ,      (self.batch_size, self.num_queries, self.mask_feature_size)  ,      )
         # let's ensure the other two hidden state exists
         self.parent.assertTrue(output.pixel_decoder_last_hidden_state is not None							)
         self.parent.assertTrue(output.encoder_last_hidden_state is not None							)

         if output_hidden_states:
           self.check_output_hidden_state(_lowerCamelCase  ,      _lowerCamelCase							)





       def       _a   ( self  ,      _lowerCamelCase  ,      _lowerCamelCase  ,      _lowerCamelCase  ,      _lowerCamelCase  ,      _lowerCamelCase							):
         UpperCamelCase_: Dict   				=    MaskFormerForInstanceSegmentation(config=_lowerCamelCase							)
         model.to(_lowerCamelCase							)
         model.eval()

         def comm_check_on_output(_lowerCamelCase							):
           # let's still check that all the required stuff is there
           self.parent.assertTrue(result.transformer_decoder_last_hidden_state is not None							)
           self.parent.assertTrue(result.pixel_decoder_last_hidden_state is not None							)
           self.parent.assertTrue(result.encoder_last_hidden_state is not None							)
           # okay, now we need to check the logits shape
           # due to the encoder compression, masks have a //4 spatial size
           self.parent.assertEqual(
               result.masks_queries_logits.shape  ,      (self.batch_size, self.num_queries, self.min_size // 4, self.max_size // 4)  ,      )
           # + 1 for null class
           self.parent.assertEqual(
               result.class_queries_logits.shape  ,      (self.batch_size, self.num_queries, self.num_labels + 1)							)

         with torch.no_grad():
           UpperCamelCase_: Tuple   				=    model(pixel_values=_lowerCamelCase  ,      pixel_mask=_lowerCamelCase							)
           UpperCamelCase_: Union[str, Any]   				=    model(_lowerCamelCase							)

           comm_check_on_output(_lowerCamelCase							)

           UpperCamelCase_: int   				=    model(
               pixel_values=_lowerCamelCase  ,      pixel_mask=_lowerCamelCase  ,      mask_labels=_lowerCamelCase  ,      class_labels=_lowerCamelCase							)

         comm_check_on_output(_lowerCamelCase							)

         self.parent.assertTrue(result.loss is not None							)
         self.parent.assertEqual(result.loss.shape  ,      torch.Size([1]							)							)







@require_torch
class     _lowerCAmelCase(	UpperCAmelCase_							,     UpperCAmelCase_							,     unittest.TestCase ):





       """simple docstring"""







       a    :		int									=(MaskFormerModel, MaskFormerForInstanceSegmentation) if is_torch_available() else ()
       a    :		Union[str, Any]									=(
           {'''feature-extraction''': MaskFormerModel, '''image-segmentation''': MaskFormerForInstanceSegmentation}
           if is_torch_available()
           else {}
       )

       a    :		int									=False
       a    :		Optional[Any]									=False
       a    :		Union[str, Any]									=False
       a    :		Dict									=False





       def       _a   ( self							):
         UpperCamelCase_: List[Any]   				=    MaskFormerModelTester(self							)
         UpperCamelCase_: Optional[int]   				=    ConfigTester(self  ,      config_class=_lowerCamelCase  ,      has_text_modality=_lowerCamelCase							)





       def       _a   ( self							):
         self.config_tester.run_common_tests()





       def       _a   ( self							):
         UpperCamelCase_				,UpperCamelCase_: Any   				=    self.model_tester.prepare_config_and_inputs_for_common()
         self.model_tester.create_and_check_maskformer_model(_lowerCamelCase  ,      **_lowerCamelCase  ,      output_hidden_states=_lowerCamelCase							)





       def       _a   ( self							):
         UpperCamelCase_: int   				=    self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_maskformer_instance_segmentation_head_model(*_lowerCamelCase							)





       @unittest.skip(reason='MaskFormer does not use inputs_embeds'							)
       def       _a   ( self							):
         pass





       @unittest.skip(reason='MaskFormer does not have a get_input_embeddings method'							)
       def       _a   ( self							):
         pass





       @unittest.skip(reason='MaskFormer is not a generative model'							)
       def       _a   ( self							):
         pass





       @unittest.skip(reason='MaskFormer does not use token embeddings'							)
       def       _a   ( self							):
         pass





       @require_torch_multi_gpu
       @unittest.skip(
           reason='MaskFormer has some layers using `add_module` which doesn\'t work well with `nn.DataParallel`'							)
       def       _a   ( self							):
         pass





       @unittest.skip('Will be fixed soon by reducing the size of the model used for common tests.'							)
       def       _a   ( self							):
         pass





       def       _a   ( self							):
         UpperCamelCase_				,UpperCamelCase_: Dict   				=    self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
           UpperCamelCase_: int   				=    model_class(_lowerCamelCase							)
           UpperCamelCase_: int   				=    inspect.signature(model.forward							)
           # signature.parameters is an OrderedDict => so arg_names order is deterministic
           UpperCamelCase_: Tuple   				=    [*signature.parameters.keys()]

           UpperCamelCase_: Tuple   				=    ['pixel_values']
           self.assertListEqual(arg_names[:1]  ,      _lowerCamelCase							)





       @slow
       def       _a   ( self							):
         for model_name in ["facebook/maskformer-swin-small-coco"]:
           UpperCamelCase_: str   				=    MaskFormerModel.from_pretrained(_lowerCamelCase							)
           self.assertIsNotNone(_lowerCamelCase							)





       def       _a   ( self							):
         UpperCamelCase_: Optional[int]   				=    (self.model_tester.min_size,) * 2
         UpperCamelCase_: List[str]   				=    {
             'pixel_values': torch.randn((2, 3, *size)  ,      device=_lowerCamelCase							),
             'mask_labels': torch.randn((2, 1_0, *size)  ,      device=_lowerCamelCase							),
             'class_labels': torch.zeros(2  ,      1_0  ,      device=_lowerCamelCase							).long(),
         }

         UpperCamelCase_: Tuple   				=    MaskFormerForInstanceSegmentation(MaskFormerConfig()							).to(_lowerCamelCase							)
         UpperCamelCase_: List[Any]   				=    model(**_lowerCamelCase							)
         self.assertTrue(outputs.loss is not None							)





       def       _a   ( self							):
         UpperCamelCase_				,UpperCamelCase_: int   				=    self.model_tester.prepare_config_and_inputs_for_common()
         self.model_tester.create_and_check_maskformer_model(_lowerCamelCase  ,      **_lowerCamelCase  ,      output_hidden_states=_lowerCamelCase							)





       def       _a   ( self							):
         UpperCamelCase_				,UpperCamelCase_: str   				=    self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
           UpperCamelCase_: List[str]   				=    model_class(_lowerCamelCase							).to(_lowerCamelCase							)
           UpperCamelCase_: List[str]   				=    model(**_lowerCamelCase  ,      output_attentions=_lowerCamelCase							)
           self.assertTrue(outputs.attentions is not None							)





       def       _a   ( self							):
         if not self.model_tester.is_training:
           return
         # only MaskFormerForInstanceSegmentation has the loss
         UpperCamelCase_: Union[str, Any]   				=    self.all_model_classes[1]
         UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_: List[Any]   				=    self.model_tester.prepare_config_and_inputs()

         UpperCamelCase_: int   				=    model_class(_lowerCamelCase							)
         model.to(_lowerCamelCase							)
         model.train()

         UpperCamelCase_: List[Any]   				=    model(_lowerCamelCase  ,      mask_labels=_lowerCamelCase  ,      class_labels=_lowerCamelCase							).loss
         loss.backward()





       def       _a   ( self							):
         # only MaskFormerForInstanceSegmentation has the loss
         UpperCamelCase_: int   				=    self.all_model_classes[1]
         UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_				,UpperCamelCase_: List[str]   				=    self.model_tester.prepare_config_and_inputs()
         UpperCamelCase_: Union[str, Any]   				=    True
         UpperCamelCase_: Dict   				=    True

         UpperCamelCase_: Optional[int]   				=    model_class(_lowerCamelCase							)
         model.to(_lowerCamelCase							)
         model.train()

         UpperCamelCase_: int   				=    model(_lowerCamelCase  ,      mask_labels=_lowerCamelCase  ,      class_labels=_lowerCamelCase							)

         UpperCamelCase_: int   				=    outputs.encoder_hidden_states[0]
         encoder_hidden_states.retain_grad()

         UpperCamelCase_: Optional[int]   				=    outputs.pixel_decoder_hidden_states[0]
         pixel_decoder_hidden_states.retain_grad()
         # we requires_grad=True in inputs_embeds (line 2152), the original implementation don't
         UpperCamelCase_: Union[str, Any]   				=    outputs.transformer_decoder_hidden_states[0]
         transformer_decoder_hidden_states.retain_grad()

         UpperCamelCase_: List[str]   				=    outputs.attentions[0]
         attentions.retain_grad()

         outputs.loss.backward(retain_graph=_lowerCamelCase							)

         self.assertIsNotNone(encoder_hidden_states.grad							)
         self.assertIsNotNone(pixel_decoder_hidden_states.grad							)
         self.assertIsNotNone(transformer_decoder_hidden_states.grad							)
         self.assertIsNotNone(attentions.grad							)







A_		:		Dict		     =			1E-4

def   snake_case ()	->    Optional[int]:
  UpperCamelCase_: List[str]   				=    Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'  )
  return image




@require_vision
@slow
class     _lowerCAmelCase(	unittest.TestCase ):





       """simple docstring"""







       @cached_property
       def       _a   ( self							):
         return (
             MaskFormerImageProcessor.from_pretrained('facebook/maskformer-swin-small-coco'							)
             if is_vision_available()
             else None
         )





       def       _a   ( self							):
         UpperCamelCase_: int   				=    MaskFormerModel.from_pretrained('facebook/maskformer-swin-small-coco'							).to(_lowerCamelCase							)
         UpperCamelCase_: int   				=    self.default_image_processor
         UpperCamelCase_: int   				=    prepare_img()
         UpperCamelCase_: List[str]   				=    image_processor(_lowerCamelCase  ,      return_tensors='pt'							).to(_lowerCamelCase							)
         UpperCamelCase_: Dict   				=    inputs['pixel_values'].shape
         # check size is divisible by 32
         self.assertTrue((inputs_shape[-1] % 3_2) == 0 and (inputs_shape[-2] % 3_2) == 0							)
         # check size
         self.assertEqual(_lowerCamelCase  ,      (1, 3, 8_0_0, 1_0_8_8)							)

         with torch.no_grad():
           UpperCamelCase_: str   				=    model(**_lowerCamelCase							)

         UpperCamelCase_: int   				=    torch.tensor(
             [[-0.0_4_8_2, 0.9_2_2_8, 0.4_9_5_1], [-0.2_5_4_7, 0.8_0_1_7, 0.8_5_2_7], [-0.0_0_6_9, 0.3_3_8_5, -0.0_0_8_9]]							).to(_lowerCamelCase							)
         self.assertTrue(
             torch.allclose(
                 outputs.encoder_last_hidden_state[0, 0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)

         UpperCamelCase_: List[str]   				=    torch.tensor(
             [[-0.8_4_2_2, -0.8_4_3_4, -0.9_7_1_8], [-1.0_1_4_4, -0.5_5_6_5, -0.4_1_9_5], [-1.0_0_3_8, -0.4_4_8_4, -0.1_9_6_1]]							).to(_lowerCamelCase							)
         self.assertTrue(
             torch.allclose(
                 outputs.pixel_decoder_last_hidden_state[0, 0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)

         UpperCamelCase_: int   				=    torch.tensor(
             [[0.2_8_5_2, -0.0_1_5_9, 0.9_7_3_5], [0.6_2_5_4, 0.1_8_5_8, 0.8_5_2_9], [-0.0_6_8_0, -0.4_1_1_6, 1.8_4_1_3]]							).to(_lowerCamelCase							)
         self.assertTrue(
             torch.allclose(
                 outputs.transformer_decoder_last_hidden_state[0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)





       def       _a   ( self							):
         UpperCamelCase_: Any   				=    (
             MaskFormerForInstanceSegmentation.from_pretrained('facebook/maskformer-swin-small-coco'							)
             .to(_lowerCamelCase							)
             .eval()
         )
         UpperCamelCase_: Union[str, Any]   				=    self.default_image_processor
         UpperCamelCase_: Optional[Any]   				=    prepare_img()
         UpperCamelCase_: str   				=    image_processor(_lowerCamelCase  ,      return_tensors='pt'							).to(_lowerCamelCase							)
         UpperCamelCase_: Optional[int]   				=    inputs['pixel_values'].shape
         # check size is divisible by 32
         self.assertTrue((inputs_shape[-1] % 3_2) == 0 and (inputs_shape[-2] % 3_2) == 0							)
         # check size
         self.assertEqual(_lowerCamelCase  ,      (1, 3, 8_0_0, 1_0_8_8)							)

         with torch.no_grad():
           UpperCamelCase_: Tuple   				=    model(**_lowerCamelCase							)
         # masks_queries_logits
         UpperCamelCase_: List[Any]   				=    outputs.masks_queries_logits
         self.assertEqual(
             masks_queries_logits.shape  ,      (1, model.config.decoder_config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)  ,      )
         UpperCamelCase_: List[str]   				=    [
             [-1.3_7_3_7_1_2_4, -1.7_7_2_4_9_3_7, -1.9_3_6_4_2_3_3],
             [-1.5_9_7_7_2_8_1, -1.9_8_6_7_9_3_9, -2.1_5_2_3_6_9_5],
             [-1.5_7_9_5_3_9_8, -1.9_2_6_9_8_3_2, -2.0_9_3_9_4_2],
         ]
         UpperCamelCase_: Optional[Any]   				=    torch.tensor(_lowerCamelCase							).to(_lowerCamelCase							)
         self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)
         # class_queries_logits
         UpperCamelCase_: Optional[Any]   				=    outputs.class_queries_logits
         self.assertEqual(
             class_queries_logits.shape  ,      (1, model.config.decoder_config.num_queries, model.config.num_labels + 1)							)
         UpperCamelCase_: int   				=    torch.tensor(
             [
                 [1.6512e00, -5.2572e00, -3.3519e00],
                 [3.6169e-02, -5.9025e00, -2.9313e00],
                 [1.0766e-04, -7.7630e00, -5.1263e00],
             ]							).to(_lowerCamelCase							)
         self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)





       def       _a   ( self							):
         UpperCamelCase_: List[Any]   				=    (
             MaskFormerForInstanceSegmentation.from_pretrained('facebook/maskformer-resnet101-coco-stuff'							)
             .to(_lowerCamelCase							)
             .eval()
         )
         UpperCamelCase_: int   				=    self.default_image_processor
         UpperCamelCase_: List[str]   				=    prepare_img()
         UpperCamelCase_: Dict   				=    image_processor(_lowerCamelCase  ,      return_tensors='pt'							).to(_lowerCamelCase							)
         UpperCamelCase_: int   				=    inputs['pixel_values'].shape
         # check size is divisible by 32
         self.assertTrue((inputs_shape[-1] % 3_2) == 0 and (inputs_shape[-2] % 3_2) == 0							)
         # check size
         self.assertEqual(_lowerCamelCase  ,      (1, 3, 8_0_0, 1_0_8_8)							)

         with torch.no_grad():
           UpperCamelCase_: List[str]   				=    model(**_lowerCamelCase							)
         # masks_queries_logits
         UpperCamelCase_: List[Any]   				=    outputs.masks_queries_logits
         self.assertEqual(
             masks_queries_logits.shape  ,      (1, model.config.decoder_config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)  ,      )
         UpperCamelCase_: Union[str, Any]   				=    [[-0.9_0_4_6, -2.6_3_6_6, -4.6_0_6_2], [-3.4_1_7_9, -5.7_8_9_0, -8.8_0_5_7], [-4.9_1_7_9, -7.6_5_6_0, -1_0.7_7_1_1]]
         UpperCamelCase_: Optional[int]   				=    torch.tensor(_lowerCamelCase							).to(_lowerCamelCase							)
         self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)
         # class_queries_logits
         UpperCamelCase_: Tuple   				=    outputs.class_queries_logits
         self.assertEqual(
             class_queries_logits.shape  ,      (1, model.config.decoder_config.num_queries, model.config.num_labels + 1)							)
         UpperCamelCase_: Union[str, Any]   				=    torch.tensor(
             [[4.7_1_8_8, -3.2_5_8_5, -2.8_8_5_7], [6.6_8_7_1, -2.9_1_8_1, -1.2_4_8_7], [7.2_4_4_9, -2.2_7_6_4, -2.1_8_7_4]]							).to(_lowerCamelCase							)
         self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3]  ,      _lowerCamelCase  ,      atol=_lowerCamelCase							)							)





       def       _a   ( self							):
         UpperCamelCase_: str   				=    (
             MaskFormerForInstanceSegmentation.from_pretrained('facebook/maskformer-swin-small-coco'							)
             .to(_lowerCamelCase							)
             .eval()
         )
         UpperCamelCase_: Union[str, Any]   				=    self.default_image_processor

         UpperCamelCase_: str   				=    image_processor(
             [np.zeros((3, 8_0_0, 1_3_3_3)							), np.zeros((3, 8_0_0, 1_3_3_3)							)]  ,      segmentation_maps=[np.zeros((3_8_4, 3_8_4)							).astype(np.floataa							), np.zeros((3_8_4, 3_8_4)							).astype(np.floataa							)]  ,      return_tensors='pt'  ,      )

         UpperCamelCase_: Dict   				=    inputs['pixel_values'].to(_lowerCamelCase							)
         UpperCamelCase_: int   				=    [el.to(_lowerCamelCase							) for el in inputs['mask_labels']]
         UpperCamelCase_: List[Any]   				=    [el.to(_lowerCamelCase							) for el in inputs['class_labels']]

         with torch.no_grad():
           UpperCamelCase_: List[str]   				=    model(**_lowerCamelCase							)

         self.assertTrue(outputs.loss is not None							)







# 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   snake_case (UpperCAmelCase__  )	->    List[str]:
  UpperCamelCase_: int   				=    [False] * len(UpperCAmelCase__  )
  UpperCamelCase_: Any   				=    [-1] * len(UpperCAmelCase__  )

  def dfs(UpperCAmelCase__     ,   UpperCAmelCase__  ):
    UpperCamelCase_: Tuple   				=    True
    UpperCamelCase_: Optional[int]   				=    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_		:		Dict		     =			{0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}
print(check_bipartite_dfs(graph))