


def   _UpperCamelCase				(						lowerCAmelCase_   )						->str:  # noqa: E741
   UpperCAmelCase							=     len(lowerCAmelCase_   )
   UpperCAmelCase							=     0
   UpperCAmelCase							=     [0] * n
   UpperCAmelCase							=     [False] * n
   UpperCAmelCase							=     [False] * n

   def dfs(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_   ):
      if parent == root:
         out_edge_count += 1
      UpperCAmelCase							=     True
      UpperCAmelCase							=     at

      for to in l[at]:
         if to == parent:
            pass
         elif not visited[to]:
            UpperCAmelCase							=     dfs(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_   )
            UpperCAmelCase							=     min(low[at]  ,						low[to]   )

            # AP found via bridge
            if at < low[to]:
               UpperCAmelCase							=     True
            # AP found via cycle
            if at == low[to]:
               UpperCAmelCase							=     True
         else:
            UpperCAmelCase							=     min(low[at]  ,						lowerCAmelCase_   )
      return out_edge_count

   for i in range(lowerCAmelCase_   ):
      if not visited[i]:
         UpperCAmelCase							=     0
         UpperCAmelCase							=     dfs(lowerCAmelCase_  ,						lowerCAmelCase_  ,						-1  ,						lowerCAmelCase_   )
         UpperCAmelCase							=     out_edge_count > 1

   for x in range(len(lowerCAmelCase_   )   ):
      if is_art[x] is True:
         print(lowerCAmelCase_   )


# Adjacency list of graph
__a     =			{
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}







compute_ap(data)







import json
import os
import shutil
import tempfile
import unittest

import numpy as np
import pytest

from transformers import CLIPTokenizer, CLIPTokenizerFast
from transformers.models.clip.tokenization_clip import VOCAB_FILES_NAMES
from transformers.testing_utils import require_vision
from transformers.utils import IMAGE_PROCESSOR_NAME, is_vision_available


if is_vision_available():
 from PIL import Image

 from transformers import OwlViTImageProcessor, OwlViTProcessor






@require_vision
class   __lowercase				(  unittest.TestCase  ):





      def        _lowercase				(		self						:					List[Any]       )    ->   Dict:






         """simple docstring"""







         UpperCAmelCase							=     tempfile.mkdtemp()

         # fmt: off
         UpperCAmelCase							=     ["""""", """l""", """o""", """w""", """e""", """r""", """s""", """t""", """i""", """d""", """n""", """lo""", """l</w>""", """w</w>""", """r</w>""", """t</w>""", """low</w>""", """er</w>""", """lowest</w>""", """newer</w>""", """wider""", """<unk>""", """<|startoftext|>""", """<|endoftext|>"""]
         # fmt: on
         UpperCAmelCase							=     dict(zip(__lowerCamelCase					,       range(len(__lowerCamelCase       )       )       )       )
         UpperCAmelCase							=     ["""#version: 0.2""", """l o""", """lo w</w>""", """e r</w>""", """"""]
         UpperCAmelCase							=     {"""unk_token""": """<unk>"""}

         UpperCAmelCase							=     os.path.join(self.tmpdirname					,       VOCAB_FILES_NAMES["""vocab_file"""]       )
         UpperCAmelCase							=     os.path.join(self.tmpdirname					,       VOCAB_FILES_NAMES["""merges_file"""]       )
         with open(self.vocab_file					,       """w"""					,       encoding="""utf-8"""       ) as fp:
            fp.write(json.dumps(__lowerCamelCase       ) + """\n"""       )
         with open(self.merges_file					,       """w"""					,       encoding="""utf-8"""       ) as fp:
            fp.write("""\n""".join(__lowerCamelCase       )       )

         UpperCAmelCase							=     {
             """do_resize""": True,
             """size""": 2_0,
             """do_center_crop""": True,
             """crop_size""": 1_8,
             """do_normalize""": True,
             """image_mean""": [0.48_145_466, 0.4_578_275, 0.40_821_073],
             """image_std""": [0.26_862_954, 0.26_130_258, 0.27_577_711],
         }
         UpperCAmelCase							=     os.path.join(self.tmpdirname					,       __lowerCamelCase       )
         with open(self.image_processor_file					,       """w"""					,       encoding="""utf-8"""       ) as fp:
            json.dump(__lowerCamelCase					,       __lowerCamelCase       )





      def        _lowercase				(		self						:					List[Any]					,       **__lowerCamelCase						:					Union[str, Any]       )    ->   int:






         """simple docstring"""







         return CLIPTokenizer.from_pretrained(self.tmpdirname					,       pad_token="""!"""					,       **__lowerCamelCase       )





      def        _lowercase				(		self						:					Optional[Any]					,       **__lowerCamelCase						:					List[str]       )    ->   str:






         """simple docstring"""







         return CLIPTokenizerFast.from_pretrained(self.tmpdirname					,       pad_token="""!"""					,       **__lowerCamelCase       )





      def        _lowercase				(		self						:					Union[str, Any]					,       **__lowerCamelCase						:					Optional[Any]       )    ->   Optional[int]:






         """simple docstring"""







         return OwlViTImageProcessor.from_pretrained(self.tmpdirname					,       **__lowerCamelCase       )





      def        _lowercase				(		self						:					Any       )    ->   List[str]:






         """simple docstring"""







         shutil.rmtree(self.tmpdirname       )





      def        _lowercase				(		self						:					List[Any]       )    ->   Optional[Any]:






         """simple docstring"""







         UpperCAmelCase							=     [np.random.randint(2_5_5					,       size=(3, 3_0, 4_0_0)					,       dtype=np.uinta       )]

         UpperCAmelCase							=     [Image.fromarray(np.moveaxis(__lowerCamelCase					,       0					,       -1       )       ) for x in image_inputs]

         return image_inputs





      def        _lowercase				(		self						:					int       )    ->   Optional[int]:






         """simple docstring"""







         UpperCAmelCase							=     self.get_tokenizer()
         UpperCAmelCase							=     self.get_rust_tokenizer()
         UpperCAmelCase							=     self.get_image_processor()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )
         processor_slow.save_pretrained(self.tmpdirname       )
         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(self.tmpdirname					,       use_fast=__lowerCamelCase       )

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )
         processor_fast.save_pretrained(self.tmpdirname       )
         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(self.tmpdirname       )

         self.assertEqual(processor_slow.tokenizer.get_vocab()					,       tokenizer_slow.get_vocab()       )
         self.assertEqual(processor_fast.tokenizer.get_vocab()					,       tokenizer_fast.get_vocab()       )
         self.assertEqual(tokenizer_slow.get_vocab()					,       tokenizer_fast.get_vocab()       )
         self.assertIsInstance(processor_slow.tokenizer					,       __lowerCamelCase       )
         self.assertIsInstance(processor_fast.tokenizer					,       __lowerCamelCase       )

         self.assertEqual(processor_slow.image_processor.to_json_string()					,       image_processor.to_json_string()       )
         self.assertEqual(processor_fast.image_processor.to_json_string()					,       image_processor.to_json_string()       )
         self.assertIsInstance(processor_slow.image_processor					,       __lowerCamelCase       )
         self.assertIsInstance(processor_fast.image_processor					,       __lowerCamelCase       )





      def        _lowercase				(		self						:					str       )    ->   Dict:






         """simple docstring"""







         UpperCAmelCase							=     OwlViTProcessor(tokenizer=self.get_tokenizer()					,       image_processor=self.get_image_processor()       )
         processor.save_pretrained(self.tmpdirname       )

         UpperCAmelCase							=     self.get_tokenizer(bos_token="""(BOS)"""					,       eos_token="""(EOS)"""       )
         UpperCAmelCase							=     self.get_image_processor(do_normalize=__lowerCamelCase       )

         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(
             self.tmpdirname					,       bos_token="""(BOS)"""					,       eos_token="""(EOS)"""					,       do_normalize=__lowerCamelCase       )

         self.assertEqual(processor.tokenizer.get_vocab()					,       tokenizer_add_kwargs.get_vocab()       )
         self.assertIsInstance(processor.tokenizer					,       __lowerCamelCase       )

         self.assertEqual(processor.image_processor.to_json_string()					,       image_processor_add_kwargs.to_json_string()       )
         self.assertIsInstance(processor.image_processor					,       __lowerCamelCase       )





      def        _lowercase				(		self						:					Any       )    ->   Union[str, Any]:






         """simple docstring"""







         UpperCAmelCase							=     self.get_image_processor()
         UpperCAmelCase							=     self.get_tokenizer()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )

         UpperCAmelCase							=     self.prepare_image_inputs()

         UpperCAmelCase							=     image_processor(__lowerCamelCase					,       return_tensors="""np"""       )
         UpperCAmelCase							=     processor(images=__lowerCamelCase					,       return_tensors="""np"""       )

         for key in input_image_proc.keys():
            self.assertAlmostEqual(input_image_proc[key].sum()					,       input_processor[key].sum()					,       delta=1e-2       )





      def        _lowercase				(		self						:					Optional[int]       )    ->   Any:






         """simple docstring"""







         UpperCAmelCase							=     self.get_image_processor()
         UpperCAmelCase							=     self.get_tokenizer()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )

         UpperCAmelCase							=     """lower newer"""

         UpperCAmelCase							=     processor(text=__lowerCamelCase					,       return_tensors="""np"""       )

         UpperCAmelCase							=     tokenizer(__lowerCamelCase					,       return_tensors="""np"""       )

         for key in encoded_tok.keys():
            self.assertListEqual(encoded_tok[key][0].tolist()					,       encoded_processor[key][0].tolist()       )





      def        _lowercase				(		self						:					Union[str, Any]       )    ->   List[str]:






         """simple docstring"""







         UpperCAmelCase							=     self.get_image_processor()
         UpperCAmelCase							=     self.get_tokenizer()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )

         UpperCAmelCase							=     """lower newer"""
         UpperCAmelCase							=     self.prepare_image_inputs()

         UpperCAmelCase							=     processor(text=__lowerCamelCase					,       images=__lowerCamelCase       )

         self.assertListEqual(list(inputs.keys()       )					,       ["""input_ids""", """attention_mask""", """pixel_values"""]       )

         # test if it raises when no input is passed
         with pytest.raises(__lowerCamelCase       ):
            processor()





      def        _lowercase				(		self						:					Optional[int]       )    ->   Any:






         """simple docstring"""







         UpperCAmelCase							=     """google/owlvit-base-patch32"""
         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(__lowerCamelCase       )

         UpperCAmelCase							=     ["""cat""", """nasa badge"""]
         UpperCAmelCase							=     processor(text=__lowerCamelCase       )

         UpperCAmelCase							=     1_6
         self.assertListEqual(list(inputs.keys()       )					,       ["""input_ids""", """attention_mask"""]       )
         self.assertEqual(inputs["""input_ids"""].shape					,       (2, seq_length)       )

         # test if it raises when no input is passed
         with pytest.raises(__lowerCamelCase       ):
            processor()





      def        _lowercase				(		self						:					Any       )    ->   int:






         """simple docstring"""







         UpperCAmelCase							=     """google/owlvit-base-patch32"""
         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(__lowerCamelCase       )

         UpperCAmelCase							=     [["""cat""", """nasa badge"""], ["""person"""]]
         UpperCAmelCase							=     processor(text=__lowerCamelCase       )

         UpperCAmelCase							=     1_6
         UpperCAmelCase							=     len(__lowerCamelCase       )
         UpperCAmelCase							=     max([len(__lowerCamelCase       ) for texts in input_texts]       )

         self.assertListEqual(list(inputs.keys()       )					,       ["""input_ids""", """attention_mask"""]       )
         self.assertEqual(inputs["""input_ids"""].shape					,       (batch_size * num_max_text_queries, seq_length)       )

         # test if it raises when no input is passed
         with pytest.raises(__lowerCamelCase       ):
            processor()





      def        _lowercase				(		self						:					Union[str, Any]       )    ->   str:






         """simple docstring"""







         UpperCAmelCase							=     """google/owlvit-base-patch32"""
         UpperCAmelCase							=     OwlViTProcessor.from_pretrained(__lowerCamelCase       )

         UpperCAmelCase							=     ["""cat""", """nasa badge"""]
         UpperCAmelCase							=     processor(text=__lowerCamelCase       )

         UpperCAmelCase							=     1_6
         UpperCAmelCase							=     inputs["""input_ids"""]
         UpperCAmelCase							=     [
             [4_9_4_0_6, 2_3_6_8, 4_9_4_0_7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [4_9_4_0_6, 6_8_4_1, 1_1_3_0_1, 4_9_4_0_7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         ]

         self.assertListEqual(list(inputs.keys()       )					,       ["""input_ids""", """attention_mask"""]       )
         self.assertEqual(inputs["""input_ids"""].shape					,       (2, seq_length)       )
         self.assertListEqual(list(input_ids[0]       )					,       predicted_ids[0]       )
         self.assertListEqual(list(input_ids[1]       )					,       predicted_ids[1]       )





      def        _lowercase				(		self						:					List[Any]       )    ->   Tuple:






         """simple docstring"""







         UpperCAmelCase							=     self.get_image_processor()
         UpperCAmelCase							=     self.get_tokenizer()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )

         UpperCAmelCase							=     self.prepare_image_inputs()
         UpperCAmelCase							=     self.prepare_image_inputs()

         UpperCAmelCase							=     processor(images=__lowerCamelCase					,       query_images=__lowerCamelCase       )

         self.assertListEqual(list(inputs.keys()       )					,       ["""query_pixel_values""", """pixel_values"""]       )

         # test if it raises when no input is passed
         with pytest.raises(__lowerCamelCase       ):
            processor()





      def        _lowercase				(		self						:					Tuple       )    ->   Any:






         """simple docstring"""







         UpperCAmelCase							=     self.get_image_processor()
         UpperCAmelCase							=     self.get_tokenizer()

         UpperCAmelCase							=     OwlViTProcessor(tokenizer=__lowerCamelCase					,       image_processor=__lowerCamelCase       )

         UpperCAmelCase							=     [[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

         UpperCAmelCase							=     processor.batch_decode(__lowerCamelCase       )
         UpperCAmelCase							=     tokenizer.batch_decode(__lowerCamelCase       )

         self.assertListEqual(__lowerCamelCase					,       __lowerCamelCase       )



