



'''simple docstring'''



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 						lowerCamelCase_				(       unittest.TestCase      ):







						def        __lowercase     (	self :   List[str]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   str         =      tempfile.mkdtemp()

													# fmt: off
													SCREAMING_SNAKE_CASE       :   Tuple         =      ['''''', '''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
													SCREAMING_SNAKE_CASE       :   Tuple         =      dict(zip(lowerCAmelCase__					,     range(len(lowerCAmelCase__					)					)					)					)
													SCREAMING_SNAKE_CASE       :   int         =      ['''#version: 0.2''', '''l o''', '''lo w</w>''', '''e r</w>''', '''''']
													SCREAMING_SNAKE_CASE       :   List[Any]         =      {'''unk_token''': '''<unk>'''}

													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      os.path.join(self.tmpdirname					,     VOCAB_FILES_NAMES['''vocab_file''']					)
													SCREAMING_SNAKE_CASE       :   str         =      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__					)					)

													SCREAMING_SNAKE_CASE       :   Tuple         =      {
													    '''do_resize''': True,
													    '''size''': 20,
													    '''do_center_crop''': True,
													    '''crop_size''': 18,
													    '''do_normalize''': True,
													    '''image_mean''': [0.4814_5466, 0.457_8275, 0.4082_1073],
													    '''image_std''': [0.2686_2954, 0.2613_0258, 0.2757_7711],
													}
													SCREAMING_SNAKE_CASE       :   Tuple         =      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 :   Any					,     **lowerCAmelCase__ :   int					):

													"""simple docstring"""
													return CLIPTokenizer.from_pretrained(self.tmpdirname					,     pad_token='''!'''					,     **lowerCAmelCase__					)







						def        __lowercase     (	self :   Optional[int]					,     **lowerCAmelCase__ :   Tuple					):

													"""simple docstring"""
													return CLIPTokenizerFast.from_pretrained(self.tmpdirname					,     pad_token='''!'''					,     **lowerCAmelCase__					)







						def        __lowercase     (	self :   List[str]					,     **lowerCAmelCase__ :   Tuple					):

													"""simple docstring"""
													return OwlViTImageProcessor.from_pretrained(self.tmpdirname					,     **lowerCAmelCase__					)







						def        __lowercase     (	self :   Union[str, Any]					):

													"""simple docstring"""
													shutil.rmtree(self.tmpdirname					)







						def        __lowercase     (	self :   List[Any]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      [np.random.randint(2_55					,     size=(3, 30, 4_00)					,     dtype=np.uinta					)]

													SCREAMING_SNAKE_CASE       :   int         =      [Image.fromarray(np.moveaxis(lowerCAmelCase__					,     0					,     -1					)					) for x in image_inputs]

													return image_inputs







						def        __lowercase     (	self :   Optional[int]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   List[Any]         =      self.get_tokenizer()
													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      self.get_rust_tokenizer()
													SCREAMING_SNAKE_CASE       :   Optional[int]         =      self.get_image_processor()

													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)
													processor_slow.save_pretrained(self.tmpdirname					)
													SCREAMING_SNAKE_CASE       :   List[str]         =      OwlViTProcessor.from_pretrained(self.tmpdirname					,     use_fast=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Optional[int]         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)
													processor_fast.save_pretrained(self.tmpdirname					)
													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      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 :   List[str]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   Any         =      OwlViTProcessor(tokenizer=self.get_tokenizer()					,     image_processor=self.get_image_processor()					)
													processor.save_pretrained(self.tmpdirname					)

													SCREAMING_SNAKE_CASE       :   str         =      self.get_tokenizer(bos_token='''(BOS)'''					,     eos_token='''(EOS)'''					)
													SCREAMING_SNAKE_CASE       :   str         =      self.get_image_processor(do_normalize=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   List[str]         =      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 :   Tuple					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   str         =      self.get_image_processor()
													SCREAMING_SNAKE_CASE       :   Optional[int]         =      self.get_tokenizer()

													SCREAMING_SNAKE_CASE       :   List[Any]         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   List[str]         =      self.prepare_image_inputs()

													SCREAMING_SNAKE_CASE       :   Tuple         =      image_processor(lowerCAmelCase__					,     return_tensors='''np'''					)
													SCREAMING_SNAKE_CASE       :   Dict         =      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 :   Tuple					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   Optional[int]         =      self.get_image_processor()
													SCREAMING_SNAKE_CASE       :   Any         =      self.get_tokenizer()

													SCREAMING_SNAKE_CASE       :   int         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   str         =      '''lower newer'''

													SCREAMING_SNAKE_CASE       :   List[Any]         =      processor(text=lowerCAmelCase__					,     return_tensors='''np'''					)

													SCREAMING_SNAKE_CASE       :   str         =      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]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   int         =      self.get_image_processor()
													SCREAMING_SNAKE_CASE       :   Tuple         =      self.get_tokenizer()

													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Optional[int]         =      '''lower newer'''
													SCREAMING_SNAKE_CASE       :   List[str]         =      self.prepare_image_inputs()

													SCREAMING_SNAKE_CASE       :   Tuple         =      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 :   List[str]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   str         =      '''google/owlvit-base-patch32'''
													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      OwlViTProcessor.from_pretrained(lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Dict         =      ['''cat''', '''nasa badge''']
													SCREAMING_SNAKE_CASE       :   List[str]         =      processor(text=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   List[Any]         =      16
													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 :   Optional[Any]					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      '''google/owlvit-base-patch32'''
													SCREAMING_SNAKE_CASE       :   str         =      OwlViTProcessor.from_pretrained(lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   List[str]         =      [['''cat''', '''nasa badge'''], ['''person''']]
													SCREAMING_SNAKE_CASE       :   Tuple         =      processor(text=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Any         =      16
													SCREAMING_SNAKE_CASE       :   Dict         =      len(lowerCAmelCase__					)
													SCREAMING_SNAKE_CASE       :   List[str]         =      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 :   Tuple					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   Dict         =      '''google/owlvit-base-patch32'''
													SCREAMING_SNAKE_CASE       :   Optional[int]         =      OwlViTProcessor.from_pretrained(lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   str         =      ['''cat''', '''nasa badge''']
													SCREAMING_SNAKE_CASE       :   List[Any]         =      processor(text=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Optional[int]         =      16
													SCREAMING_SNAKE_CASE       :   str         =      inputs['''input_ids''']
													SCREAMING_SNAKE_CASE       :   Dict         =      [
													    [4_94_06, 23_68, 4_94_07, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
													    [4_94_06, 68_41, 1_13_01, 4_94_07, 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 :   Tuple					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   List[Any]         =      self.get_image_processor()
													SCREAMING_SNAKE_CASE       :   Optional[Any]         =      self.get_tokenizer()

													SCREAMING_SNAKE_CASE       :   List[str]         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      self.prepare_image_inputs()
													SCREAMING_SNAKE_CASE       :   Dict         =      self.prepare_image_inputs()

													SCREAMING_SNAKE_CASE       :   str         =      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 :   int					):

													"""simple docstring"""
													SCREAMING_SNAKE_CASE       :   str         =      self.get_image_processor()
													SCREAMING_SNAKE_CASE       :   str         =      self.get_tokenizer()

													SCREAMING_SNAKE_CASE       :   str         =      OwlViTProcessor(tokenizer=lowerCAmelCase__					,     image_processor=lowerCAmelCase__					)

													SCREAMING_SNAKE_CASE       :   Optional[Any]         =      [[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

													SCREAMING_SNAKE_CASE       :   List[Any]         =      processor.batch_decode(lowerCAmelCase__					)
													SCREAMING_SNAKE_CASE       :   Optional[int]         =      tokenizer.batch_decode(lowerCAmelCase__					)

													self.assertListEqual(lowerCAmelCase__					,     lowerCAmelCase__					)









'''simple docstring'''



from collections import defaultdict
def        UpperCAmelCase (    A	:					int					):
							SCREAMING_SNAKE_CASE       :   List[Any]         =      1
							SCREAMING_SNAKE_CASE       :   Dict         =      True
							for v in tree[start]:
														if v not in visited:
																					ret += dfs(A					)
							if ret % 2 == 0:
														cuts.append(A					)
							return ret
def        UpperCAmelCase (    ):
							dfs(1					)


if __name__ == "__main__":
							lowerCAmelCase_      ,				lowerCAmelCase_  :							Dict             =    10, 9
							lowerCAmelCase_  :							Dict             =    defaultdict(list)
							lowerCAmelCase_  :							dict[int, bool]             =    {}
							lowerCAmelCase_  :							list[int]             =    []
							lowerCAmelCase_  :							Optional[Any]             =    0
							lowerCAmelCase_  :							Dict             =    [(2, 1), (3, 1), (4, 3), (5, 2), (6, 1), (7, 2), (8, 6), (9, 8), (10, 8)]
							for u, v in edges:
														tree[u].append(v)
														tree[v].append(u)
							even_tree()
							print(len(cuts) - 1)




