


'''simple docstring'''



import os
import sys
import unittest


__lowercase      :		Dict			=      os.path.abspath(os.path.dirname(os.path.dirname(os.path.dirname(__file__))))
sys.path.append(os.path.join(git_repo_path, 'utils'))

import check_dummies  # noqa: E402
from check_dummies import create_dummy_files, create_dummy_object, find_backend, read_init  # noqa: E402


# Align TRANSFORMERS_PATH in check_dummies with the current path
__lowercase      :		Any			=      os.path.join(git_repo_path, 'src', 'transformers')

__lowercase      :		int			=      '\n{0} = None\n'

__lowercase      :		Optional[Any]			=      '\nclass {0}(metaclass=DummyObject):\n    _backends = {1}\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, {1})\n'


__lowercase      :		Union[str, Any]			=      '\ndef {0}(*args, **kwargs):\n    requires_backends({0}, {1})\n'





class 				__UpperCamelCase							(						unittest.TestCase   ):




	def  __UpperCAmelCase				(  self				):

						'''simple docstring'''





						__a     :			Dict          =    find_backend('    _import_structure["models.albert"].append("AlbertTokenizerFast")'				)
						self.assertIsNone(lowerCAmelCase__				)

						__a     :			Any          =    find_backend('    if not is_tokenizers_available():'				)
						self.assertEqual(lowerCAmelCase__		,							'tokenizers'				)

						__a     :			Optional[int]          =    find_backend('    if not is_tensorflow_text_available():'				)
						self.assertEqual(lowerCAmelCase__		,							'tensorflow_text'				)

						__a     :			Union[str, Any]          =    find_backend('    if not (is_sentencepiece_available() and is_tokenizers_available()):'				)
						self.assertEqual(lowerCAmelCase__		,							'sentencepiece_and_tokenizers'				)

						__a     :			Optional[Any]          =    find_backend(
						    '    if not (is_sentencepiece_available() and is_tensorflow_text_available()):'				)
						self.assertEqual(lowerCAmelCase__		,							'sentencepiece_and_tensorflow_text'				)

						__a     :			List[Any]          =    find_backend(
						    '    if not (is_sentencepiece_available() and is_tokenizers_available() and is_vision_available()):'				)
						self.assertEqual(lowerCAmelCase__		,							'sentencepiece_and_tokenizers_and_vision'				)




	def  __UpperCAmelCase				(  self				):

						'''simple docstring'''





						__a     :			List[Any]          =    read_init()
						# We don't assert on the exact list of keys to allow for smooth grow of backend-specific objects
						self.assertIn('torch'		,							lowerCAmelCase__				)
						self.assertIn('tensorflow_text'		,							lowerCAmelCase__				)
						self.assertIn('sentencepiece_and_tokenizers'		,							lowerCAmelCase__				)

						# Likewise, we can't assert on the exact content of a key
						self.assertIn('BertModel'		,							objects['torch']				)
						self.assertIn('TFBertModel'		,							objects['tf']				)
						self.assertIn('FlaxBertModel'		,							objects['flax']				)
						self.assertIn('BertModel'		,							objects['torch']				)
						self.assertIn('TFBertTokenizer'		,							objects['tensorflow_text']				)
						self.assertIn('convert_slow_tokenizer'		,							objects['sentencepiece_and_tokenizers']				)




	def  __UpperCAmelCase				(  self				):

						'''simple docstring'''





						__a     :			Dict          =    create_dummy_object('CONSTANT'		,							'\'torch\''				)
						self.assertEqual(lowerCAmelCase__		,							'\nCONSTANT = None\n'				)

						__a     :			Dict          =    create_dummy_object('function'		,							'\'torch\''				)
						self.assertEqual(
						    lowerCAmelCase__		,							'\ndef function(*args, **kwargs):\n    requires_backends(function, \'torch\')\n'				)

						__a     :			Optional[int]          =    '''
class FakeClass(metaclass=DummyObject):
    _backends = \'torch\'

    def __init__(self, *args, **kwargs):
        requires_backends(self, \'torch\')
'''
						__a     :			Union[str, Any]          =    create_dummy_object('FakeClass'		,							'\'torch\''				)
						self.assertEqual(lowerCAmelCase__		,							lowerCAmelCase__				)





	def  __UpperCAmelCase				(  self				):

						'''simple docstring'''





						__a     :			Dict          =    '''# This file is autogenerated by the command `make fix-copies`, do not edit.
from ..utils import DummyObject, requires_backends


CONSTANT = None


def function(*args, **kwargs):
    requires_backends(function, ["torch"])


class FakeClass(metaclass=DummyObject):
    _backends = ["torch"]

    def __init__(self, *args, **kwargs):
        requires_backends(self, ["torch"])
'''
						__a     :			Optional[Any]          =    create_dummy_files({'torch': ['CONSTANT', 'function', 'FakeClass']}				)
						self.assertEqual(dummy_files['torch']		,							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)




