




import os
import sys
import tempfile
import unittest
import unittest.mock as mock
from pathlib import Path

from huggingface_hub import HfFolder, delete_repo
from huggingface_hub.file_download import http_get
from requests.exceptions import HTTPError

from transformers import (
    AlbertTokenizer,
    AutoTokenizer,
    BertTokenizer,
    BertTokenizerFast,
    GPTaTokenizerFast,
    is_tokenizers_available,
)
from transformers.testing_utils import TOKEN, USER, is_staging_test, require_tokenizers
from transformers.tokenization_utils import Trie


sys.path.append(str(Path(__file__).parent.parent / '''utils'''))

from test_module.custom_tokenization import CustomTokenizer  # noqa E402


if is_tokenizers_available():
	from test_module.custom_tokenization_fast import CustomTokenizerFast


class    SCREAMING_SNAKE_CASE_				(       unittest.TestCase   ):



	"""simple docstring"""


	def 					lowerCamelCase__     (					self		:						Any	)	->       int:







						"""simple docstring"""







						__UpperCamelCase					:	List[str]             =      mock.Mock()
						__UpperCamelCase					:	List[Any]             =      500
						__UpperCamelCase					:	List[Any]             =      {}
						__UpperCamelCase					:	Optional[int]             =      HTTPError
						__UpperCamelCase					:	Dict             =      {}

						# Download this model to make sure it's in the cache.
						__UpperCamelCase					:	List[Any]             =      BertTokenizer.from_pretrained("""hf-internal-testing/tiny-random-bert"""	)

						# Under the mock environment we get a 500 error when trying to reach the tokenizer.
						with mock.patch("""requests.Session.request"""					,     return_value=lowerCAmelCase	) as mock_head:
											__UpperCamelCase					:	Union[str, Any]             =      BertTokenizer.from_pretrained("""hf-internal-testing/tiny-random-bert"""	)
											# This check we did call the fake head request
											mock_head.assert_called()






	@require_tokenizers
	def 					lowerCamelCase__     (					self		:						Optional[int]	)	->       Any:







						"""simple docstring"""







						__UpperCamelCase					:	Optional[Any]             =      mock.Mock()
						__UpperCamelCase					:	str             =      500
						__UpperCamelCase					:	Dict             =      {}
						__UpperCamelCase					:	Union[str, Any]             =      HTTPError
						__UpperCamelCase					:	Optional[int]             =      {}

						# Download this model to make sure it's in the cache.
						__UpperCamelCase					:	List[str]             =      GPTaTokenizerFast.from_pretrained("""gpt2"""	)

						# Under the mock environment we get a 500 error when trying to reach the tokenizer.
						with mock.patch("""requests.Session.request"""					,     return_value=lowerCAmelCase	) as mock_head:
											__UpperCamelCase					:	Union[str, Any]             =      GPTaTokenizerFast.from_pretrained("""gpt2"""	)
											# This check we did call the fake head request
											mock_head.assert_called()






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







						"""simple docstring"""







						try:
											__UpperCamelCase					:	str             =      tempfile.mktemp()
											with open(lowerCAmelCase					,     """wb"""	) as f:
																http_get("""https://huggingface.co/albert-base-v1/resolve/main/spiece.model"""					,     lowerCAmelCase	)

											__UpperCamelCase					:	str             =      AlbertTokenizer.from_pretrained(lowerCAmelCase	)
						finally:
											os.remove(lowerCAmelCase	)

						# Supporting this legacy load introduced a weird bug where the tokenizer would load local files if they are in
						# the current folder and have the right name.
						if os.path.isfile("""tokenizer.json"""	):
											# We skip the test if the user has a `tokenizer.json` in this folder to avoid deleting it.
											return
						try:
											with open("""tokenizer.json"""					,     """wb"""	) as f:
																http_get("""https://huggingface.co/hf-internal-testing/tiny-random-bert/blob/main/tokenizer.json"""					,     lowerCAmelCase	)
											__UpperCamelCase					:	Tuple             =      AutoTokenizer.from_pretrained("""hf-internal-testing/tiny-random-gpt2"""	)
											# The tiny random BERT has a vocab size of 1024, tiny gpt2 as a vocab size of 1000
											self.assertEqual(tokenizer.vocab_size					,     1000	)
											# Tokenizer should depend on the remote checkpoint, not the local tokenizer.json file.

						finally:
											os.remove("""tokenizer.json"""	)






	def 					lowerCamelCase__     (					self		:						Dict	)	->       Optional[int]:







						"""simple docstring"""







						__UpperCamelCase					:	List[Any]             =      AlbertTokenizer.from_pretrained("""https://huggingface.co/albert-base-v1/resolve/main/spiece.model"""	)






@is_staging_test
class    SCREAMING_SNAKE_CASE_				(       unittest.TestCase   ):



	"""simple docstring"""


	__magic_name__   :       Optional[Any]      	=		['[UNK]', '[CLS]', '[SEP]', '[PAD]', '[MASK]', 'bla', 'blou']






	@classmethod
	def 					lowerCamelCase__     (					cls		:						Tuple	)	->       List[str]:







						"""simple docstring"""







						__UpperCamelCase					:	List[Any]             =      TOKEN
						HfFolder.save_token(lowerCAmelCase	)






	@classmethod
	def 					lowerCamelCase__     (					cls		:						List[Any]	)	->       int:







						"""simple docstring"""







						try:
											delete_repo(token=cls._token					,     repo_id="""test-tokenizer"""	)
						except HTTPError:
											pass

						try:
											delete_repo(token=cls._token					,     repo_id="""valid_org/test-tokenizer-org"""	)
						except HTTPError:
											pass

						try:
											delete_repo(token=cls._token					,     repo_id="""test-dynamic-tokenizer"""	)
						except HTTPError:
											pass






	def 					lowerCamelCase__     (					self		:						Dict	)	->       Optional[int]:







						"""simple docstring"""







						with tempfile.TemporaryDirectory() as tmp_dir:
											__UpperCamelCase					:	Optional[int]             =      os.path.join(lowerCAmelCase					,     """vocab.txt"""	)
											with open(lowerCAmelCase					,     """w"""					,     encoding="""utf-8"""	) as vocab_writer:
																vocab_writer.write("""""".join([x + """\n""" for x in self.vocab_tokens]	)	)
											__UpperCamelCase					:	int             =      BertTokenizer(lowerCAmelCase	)

						tokenizer.push_to_hub("""test-tokenizer"""					,     use_auth_token=self._token	)
						__UpperCamelCase					:	List[Any]             =      BertTokenizer.from_pretrained(F'''{USER}/test-tokenizer'''	)
						self.assertDictEqual(new_tokenizer.vocab					,     tokenizer.vocab	)

						# Reset repo
						delete_repo(token=self._token					,     repo_id="""test-tokenizer"""	)

						# Push to hub via save_pretrained
						with tempfile.TemporaryDirectory() as tmp_dir:
											tokenizer.save_pretrained(lowerCAmelCase					,     repo_id="""test-tokenizer"""					,     push_to_hub=lowerCAmelCase					,     use_auth_token=self._token	)

						__UpperCamelCase					:	Any             =      BertTokenizer.from_pretrained(F'''{USER}/test-tokenizer'''	)
						self.assertDictEqual(new_tokenizer.vocab					,     tokenizer.vocab	)






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







						"""simple docstring"""







						with tempfile.TemporaryDirectory() as tmp_dir:
											__UpperCamelCase					:	int             =      os.path.join(lowerCAmelCase					,     """vocab.txt"""	)
											with open(lowerCAmelCase					,     """w"""					,     encoding="""utf-8"""	) as vocab_writer:
																vocab_writer.write("""""".join([x + """\n""" for x in self.vocab_tokens]	)	)
											__UpperCamelCase					:	List[str]             =      BertTokenizer(lowerCAmelCase	)

						tokenizer.push_to_hub("""valid_org/test-tokenizer-org"""					,     use_auth_token=self._token	)
						__UpperCamelCase					:	Optional[Any]             =      BertTokenizer.from_pretrained("""valid_org/test-tokenizer-org"""	)
						self.assertDictEqual(new_tokenizer.vocab					,     tokenizer.vocab	)

						# Reset repo
						delete_repo(token=self._token					,     repo_id="""valid_org/test-tokenizer-org"""	)

						# Push to hub via save_pretrained
						with tempfile.TemporaryDirectory() as tmp_dir:
											tokenizer.save_pretrained(
											    lowerCAmelCase					,     repo_id="""valid_org/test-tokenizer-org"""					,     push_to_hub=lowerCAmelCase					,     use_auth_token=self._token	)

						__UpperCamelCase					:	str             =      BertTokenizer.from_pretrained("""valid_org/test-tokenizer-org"""	)
						self.assertDictEqual(new_tokenizer.vocab					,     tokenizer.vocab	)






	@require_tokenizers
	def 					lowerCamelCase__     (					self		:						Dict	)	->       Tuple:







						"""simple docstring"""







						CustomTokenizer.register_for_auto_class()
						with tempfile.TemporaryDirectory() as tmp_dir:
											__UpperCamelCase					:	Any             =      os.path.join(lowerCAmelCase					,     """vocab.txt"""	)
											with open(lowerCAmelCase					,     """w"""					,     encoding="""utf-8"""	) as vocab_writer:
																vocab_writer.write("""""".join([x + """\n""" for x in self.vocab_tokens]	)	)
											__UpperCamelCase					:	Union[str, Any]             =      CustomTokenizer(lowerCAmelCase	)

						# No fast custom tokenizer
						tokenizer.push_to_hub("""test-dynamic-tokenizer"""					,     use_auth_token=self._token	)

						__UpperCamelCase					:	Optional[int]             =      AutoTokenizer.from_pretrained(F'''{USER}/test-dynamic-tokenizer'''					,     trust_remote_code=lowerCAmelCase	)
						# Can't make an isinstance check because the new_model.config is from the CustomTokenizer class of a dynamic module
						self.assertEqual(tokenizer.__class__.__name__					,     """CustomTokenizer"""	)

						# Fast and slow custom tokenizer
						CustomTokenizerFast.register_for_auto_class()
						with tempfile.TemporaryDirectory() as tmp_dir:
											__UpperCamelCase					:	str             =      os.path.join(lowerCAmelCase					,     """vocab.txt"""	)
											with open(lowerCAmelCase					,     """w"""					,     encoding="""utf-8"""	) as vocab_writer:
																vocab_writer.write("""""".join([x + """\n""" for x in self.vocab_tokens]	)	)

											__UpperCamelCase					:	str             =      BertTokenizerFast.from_pretrained(lowerCAmelCase	)
											bert_tokenizer.save_pretrained(lowerCAmelCase	)
											__UpperCamelCase					:	Tuple             =      CustomTokenizerFast.from_pretrained(lowerCAmelCase	)

						tokenizer.push_to_hub("""test-dynamic-tokenizer"""					,     use_auth_token=self._token	)

						__UpperCamelCase					:	List[Any]             =      AutoTokenizer.from_pretrained(F'''{USER}/test-dynamic-tokenizer'''					,     trust_remote_code=lowerCAmelCase	)
						# Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
						self.assertEqual(tokenizer.__class__.__name__					,     """CustomTokenizerFast"""	)
						__UpperCamelCase					:	List[str]             =      AutoTokenizer.from_pretrained(
						    F'''{USER}/test-dynamic-tokenizer'''					,     use_fast=lowerCAmelCase					,     trust_remote_code=lowerCAmelCase	)
						# Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
						self.assertEqual(tokenizer.__class__.__name__					,     """CustomTokenizer"""	)






class    SCREAMING_SNAKE_CASE_				(       unittest.TestCase   ):



	"""simple docstring"""


	def 					lowerCamelCase__     (					self		:						List[str]	)	->       List[str]:







						"""simple docstring"""







						__UpperCamelCase					:	Optional[int]             =      Trie()
						trie.add("""Hello 友達"""	)
						self.assertEqual(trie.data					,     {"""H""": {"""e""": {"""l""": {"""l""": {"""o""": {""" """: {"""友""": {"""達""": {"""""": 1}}}}}}}}}	)
						trie.add("""Hello"""	)
						trie.data
						self.assertEqual(trie.data					,     {"""H""": {"""e""": {"""l""": {"""l""": {"""o""": {"""""": 1, """ """: {"""友""": {"""達""": {"""""": 1}}}}}}}}}	)






	def 					lowerCamelCase__     (					self		:						Any	)	->       Optional[Any]:







						"""simple docstring"""







						__UpperCamelCase					:	Dict             =      Trie()
						self.assertEqual(trie.split("""[CLS] This is a extra_id_100"""	)					,     ["""[CLS] This is a extra_id_100"""]	)
						trie.add("""[CLS]"""	)
						trie.add("""extra_id_1"""	)
						trie.add("""extra_id_100"""	)
						self.assertEqual(trie.split("""[CLS] This is a extra_id_100"""	)					,     ["""[CLS]""", """ This is a """, """extra_id_100"""]	)






	def 					lowerCamelCase__     (					self		:						Tuple	)	->       Tuple:







						"""simple docstring"""







						__UpperCamelCase					:	Dict             =      Trie()
						trie.add("""A"""	)
						self.assertEqual(trie.split("""ABC"""	)					,     ["""A""", """BC"""]	)
						self.assertEqual(trie.split("""BCA"""	)					,     ["""BC""", """A"""]	)






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







						"""simple docstring"""







						__UpperCamelCase					:	Optional[Any]             =      Trie()
						trie.add("""TOKEN]"""	)
						trie.add("""[SPECIAL_TOKEN]"""	)
						self.assertEqual(trie.split("""This is something [SPECIAL_TOKEN]"""	)					,     ["""This is something """, """[SPECIAL_TOKEN]"""]	)






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







						"""simple docstring"""







						__UpperCamelCase					:	Tuple             =      Trie()
						trie.add("""A"""	)
						trie.add("""P"""	)
						trie.add("""[SPECIAL_TOKEN]"""	)
						self.assertEqual(trie.split("""This is something [SPECIAL_TOKEN]"""	)					,     ["""This is something """, """[SPECIAL_TOKEN]"""]	)






	def 					lowerCamelCase__     (					self		:						Any	)	->       Any:







						"""simple docstring"""







						__UpperCamelCase					:	List[str]             =      Trie()
						trie.add("""AB"""	)
						trie.add("""B"""	)
						trie.add("""C"""	)
						self.assertEqual(trie.split("""ABC"""	)					,     ["""AB""", """C"""]	)






	def 					lowerCamelCase__     (					self		:						int	)	->       str:







						"""simple docstring"""







						__UpperCamelCase					:	Optional[Any]             =      Trie()
						trie.add("""ABC"""	)
						trie.add("""B"""	)
						trie.add("""CD"""	)
						self.assertEqual(trie.split("""ABCD"""	)					,     ["""ABC""", """D"""]	)






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







						"""simple docstring"""







						__UpperCamelCase					:	Optional[Any]             =      Trie()
						__UpperCamelCase					:	Optional[Any]             =      trie.cut_text("""ABC"""					,     [0, 0, 2, 1, 2, 3]	)
						self.assertEqual(lowerCAmelCase					,     ["""AB""", """C"""]	)












from collections import defaultdict





def 				A__ (snake_case   :		int				)     ->						int:
					__UpperCamelCase					:	Optional[int]             =      1
					__UpperCamelCase					:	Tuple             =      True
					for v in tree[start]:
										if v not in visited:
															ret += dfs(snake_case				)
					if ret % 2 == 0:
										cuts.append(snake_case				)
					return ret





def 				A__ ()     ->						str:
					dfs(1				)


if __name__ == "__main__":
	a__     ,							a__		     =     10, 9
	a__		     =     defaultdict(list)
	a__		     =     {}
	a__		     =     []
	a__		     =     0
	a__		     =     [(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)






