






from collections import defaultdict

def      lowerCAmelCase__	(    _a       :			Optional[int]    ):
		snake_case_				:							Optional[Any]						 =       1
		snake_case_				:							Optional[int]						 =       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      lowerCAmelCase__	(    ):
		dfs(1    )


if __name__ == "__main__":
							lowercase  ,lowercase  :							int			  =    10, 9
							lowercase  :							List[str]			  =    defaultdict(list)
							lowercase  :							Dict			  =    {}
							lowercase  :							Optional[Any]			  =    []
							lowercase  :							Union[str, Any]			  =    0
							lowercase  :							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)








import os
import unittest

from transformers import BertTokenizerFast
from transformers.models.bert.tokenization_bert import (
    VOCAB_FILES_NAMES,
    BasicTokenizer,
    BertTokenizer,
    WordpieceTokenizer,
    _is_control,
    _is_punctuation,
    _is_whitespace,
)
from transformers.testing_utils import require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin, filter_non_english




@require_tokenizers
class 		UpperCAmelCase_						(	SCREAMING_SNAKE_CASE__					,  unittest.TestCase					):


						'''simple docstring'''




						A     :   str						=					BertTokenizer
						A     :   Union[str, Any]						=					BertTokenizerFast
						A     :   int						=					True
						A     :   Union[str, Any]						=					True
						A     :   Union[str, Any]						=					filter_non_english






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								super().setUp()

								snake_case_				:							Optional[int]						 =       [
								    "[UNK]",
								    "[CLS]",
								    "[SEP]",
								    "[PAD]",
								    "[MASK]",
								    "want",
								    "##want",
								    "##ed",
								    "wa",
								    "un",
								    "runn",
								    "##ing",
								    ",",
								    "low",
								    "lowest",
								]
								snake_case_				:							str						 =       os.path.join(self.tmpdirname		,				VOCAB_FILES_NAMES["vocab_file"]				)
								with open(self.vocab_file		,				"w"		,				encoding="utf-8"				) as vocab_writer:
										vocab_writer.write("".join([x + "\n" for x in vocab_tokens]				)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE				) ->				Tuple:
								snake_case_				:							str						 =       "UNwant\u00E9d,running"
								snake_case_				:							Optional[int]						 =       "unwanted, running"
								return input_text, output_text






						def       _lowerCAmelCase       (	self				) ->				str:
								snake_case_				:							str						 =       self.tokenizer_class(self.vocab_file				)

								snake_case_				:							Tuple						 =       tokenizer.tokenize("UNwant\u00E9d,running"				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				["un", "##want", "##ed", ",", "runn", "##ing"]				)
								self.assertListEqual(tokenizer.convert_tokens_to_ids(_SCREAMING_SNAKE_CASE				)		,				[9, 6, 7, 12, 10, 11]				)






						def       _lowerCAmelCase       (	self				) ->				Optional[Any]:
								if not self.test_rust_tokenizer:
										return

								snake_case_				:							Any						 =       self.get_tokenizer()
								snake_case_				:							str						 =       self.get_rust_tokenizer()

								snake_case_				:							List[Any]						 =       "UNwant\u00E9d,running"

								snake_case_				:							Union[str, Any]						 =       tokenizer.tokenize(_SCREAMING_SNAKE_CASE				)
								snake_case_				:							int						 =       rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								snake_case_				:							str						 =       tokenizer.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
								snake_case_				:							str						 =       rust_tokenizer.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								snake_case_				:							int						 =       self.get_rust_tokenizer()
								snake_case_				:							Any						 =       tokenizer.encode(_SCREAMING_SNAKE_CASE				)
								snake_case_				:							Any						 =       rust_tokenizer.encode(_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								# With lower casing
								snake_case_				:							Tuple						 =       self.get_tokenizer(do_lower_case=_SCREAMING_SNAKE_CASE				)
								snake_case_				:							Any						 =       self.get_rust_tokenizer(do_lower_case=_SCREAMING_SNAKE_CASE				)

								snake_case_				:							Tuple						 =       "UNwant\u00E9d,running"

								snake_case_				:							Tuple						 =       tokenizer.tokenize(_SCREAMING_SNAKE_CASE				)
								snake_case_				:							int						 =       rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								snake_case_				:							List[Any]						 =       tokenizer.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
								snake_case_				:							int						 =       rust_tokenizer.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								snake_case_				:							Optional[int]						 =       self.get_rust_tokenizer()
								snake_case_				:							Dict						 =       tokenizer.encode(_SCREAMING_SNAKE_CASE				)
								snake_case_				:							str						 =       rust_tokenizer.encode(_SCREAMING_SNAKE_CASE				)
								self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)






						def       _lowerCAmelCase       (	self				) ->				List[Any]:
								snake_case_				:							Union[str, Any]						 =       BasicTokenizer()

								self.assertListEqual(tokenizer.tokenize("ah\u535A\u63A8zz"				)		,				["ah", "\u535A", "\u63A8", "zz"]				)






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							List[Any]						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHeLLo!how  \n Are yoU?  "				)		,				["hello", "!", "how", "are", "you", "?"]				)
								self.assertListEqual(tokenizer.tokenize("H\u00E9llo"				)		,				["hello"]				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								snake_case_				:							List[str]						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE		,				strip_accents=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "				)		,				["hällo", "!", "how", "are", "you", "?"]				)
								self.assertListEqual(tokenizer.tokenize("H\u00E9llo"				)		,				["h\u00E9llo"]				)






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							Optional[Any]						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE		,				strip_accents=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "				)		,				["hallo", "!", "how", "are", "you", "?"]				)
								self.assertListEqual(tokenizer.tokenize("H\u00E9llo"				)		,				["hello"]				)






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							Dict						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "				)		,				["hallo", "!", "how", "are", "you", "?"]				)
								self.assertListEqual(tokenizer.tokenize("H\u00E9llo"				)		,				["hello"]				)






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							List[str]						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHeLLo!how  \n Are yoU?  "				)		,				["HeLLo", "!", "how", "Are", "yoU", "?"]				)






						def       _lowerCAmelCase       (	self				) ->				int:
								snake_case_				:							str						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE		,				strip_accents=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "				)		,				["HäLLo", "!", "how", "Are", "yoU", "?"]				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								snake_case_				:							str						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE		,				strip_accents=_SCREAMING_SNAKE_CASE				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "				)		,				["HaLLo", "!", "how", "Are", "yoU", "?"]				)






						def       _lowerCAmelCase       (	self				) ->				Union[str, Any]:
								snake_case_				:							Any						 =       BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE		,				never_split=["[UNK]"]				)

								self.assertListEqual(
								    tokenizer.tokenize(" \tHeLLo!how  \n Are yoU? [UNK]"				)		,				["HeLLo", "!", "how", "Are", "yoU", "?", "[UNK]"]				)






						def       _lowerCAmelCase       (	self				) ->				Optional[Any]:
								snake_case_				:							Optional[Any]						 =       BasicTokenizer()
								snake_case_				:							Optional[Any]						 =       "a\n'll !!to?'d of, can't."
								snake_case_				:							Tuple						 =       ["a", "'", "ll", "!", "!", "to", "?", "'", "d", "of", ",", "can", "'", "t", "."]
								self.assertListEqual(tokenizer.tokenize(_SCREAMING_SNAKE_CASE				)		,				_SCREAMING_SNAKE_CASE				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								snake_case_				:							List[Any]						 =       ["[UNK]", "[CLS]", "[SEP]", "want", "##want", "##ed", "wa", "un", "runn", "##ing"]

								snake_case_				:							Optional[int]						 =       {}
								for i, token in enumerate(_SCREAMING_SNAKE_CASE				):
										snake_case_				:							Any						 =       i
								snake_case_				:							Any						 =       WordpieceTokenizer(vocab=_SCREAMING_SNAKE_CASE		,				unk_token="[UNK]"				)

								self.assertListEqual(tokenizer.tokenize(""				)		,				[]				)

								self.assertListEqual(tokenizer.tokenize("unwanted running"				)		,				["un", "##want", "##ed", "runn", "##ing"]				)

								self.assertListEqual(tokenizer.tokenize("unwantedX running"				)		,				["[UNK]", "runn", "##ing"]				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								self.assertTrue(_is_whitespace(" "				)				)
								self.assertTrue(_is_whitespace("\t"				)				)
								self.assertTrue(_is_whitespace("\r"				)				)
								self.assertTrue(_is_whitespace("\n"				)				)
								self.assertTrue(_is_whitespace("\u00A0"				)				)

								self.assertFalse(_is_whitespace("A"				)				)
								self.assertFalse(_is_whitespace("-"				)				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								self.assertTrue(_is_control("\u0005"				)				)

								self.assertFalse(_is_control("A"				)				)
								self.assertFalse(_is_control(" "				)				)
								self.assertFalse(_is_control("\t"				)				)
								self.assertFalse(_is_control("\r"				)				)






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								self.assertTrue(_is_punctuation("-"				)				)
								self.assertTrue(_is_punctuation("$"				)				)
								self.assertTrue(_is_punctuation("`"				)				)
								self.assertTrue(_is_punctuation("."				)				)

								self.assertFalse(_is_punctuation("A"				)				)
								self.assertFalse(_is_punctuation(" "				)				)






						def       _lowerCAmelCase       (	self				) ->				Optional[int]:
								snake_case_				:							Dict						 =       self.get_tokenizer()
								snake_case_				:							Any						 =       self.get_rust_tokenizer()

								# Example taken from the issue https://github.com/huggingface/tokenizers/issues/340
								self.assertListEqual([tokenizer.tokenize(_SCREAMING_SNAKE_CASE				) for t in ["Test", "\xad", "test"]]		,				[["[UNK]"], [], ["[UNK]"]]				)

								self.assertListEqual(
								    [rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE				) for t in ["Test", "\xad", "test"]]		,				[["[UNK]"], [], ["[UNK]"]]				)






						@slow
						def       _lowerCAmelCase       (	self				) ->				Optional[int]:
								snake_case_				:							Union[str, Any]						 =       self.tokenizer_class.from_pretrained("bert-base-uncased"				)

								snake_case_				:							Tuple						 =       tokenizer.encode("sequence builders"		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
								snake_case_				:							List[Any]						 =       tokenizer.encode("multi-sequence build"		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)

								snake_case_				:							Optional[Any]						 =       tokenizer.build_inputs_with_special_tokens(_SCREAMING_SNAKE_CASE				)
								snake_case_				:							Union[str, Any]						 =       tokenizer.build_inputs_with_special_tokens(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

								assert encoded_sentence == [101] + text + [102]
								assert encoded_pair == [101] + text + [102] + text_a + [102]






						def       _lowerCAmelCase       (	self				) ->				int:
								for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
										with self.subTest(f'''{tokenizer.__class__.__name__} ({pretrained_name})'''				):
												snake_case_				:							Union[str, Any]						 =       self.rust_tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE		,				**_SCREAMING_SNAKE_CASE				)

												snake_case_				:							List[Any]						 =       f'''A, naïve {tokenizer_r.mask_token} AllenNLP sentence.'''
												snake_case_				:							List[Any]						 =       tokenizer_r.encode_plus(
												    _SCREAMING_SNAKE_CASE		,				return_attention_mask=_SCREAMING_SNAKE_CASE		,				return_token_type_ids=_SCREAMING_SNAKE_CASE		,				return_offsets_mapping=_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE		,				)

												snake_case_				:							Optional[Any]						 =       tokenizer_r.do_lower_case if hasattr(_SCREAMING_SNAKE_CASE		,				"do_lower_case"				) else False
												snake_case_				:							Union[str, Any]						 =       (
												    [
												        ((0, 0), tokenizer_r.cls_token),
												        ((0, 1), "A"),
												        ((1, 2), ","),
												        ((3, 5), "na"),
												        ((5, 6), "##ï"),
												        ((6, 8), "##ve"),
												        ((9, 15), tokenizer_r.mask_token),
												        ((16, 21), "Allen"),
												        ((21, 23), "##NL"),
												        ((23, 24), "##P"),
												        ((25, 33), "sentence"),
												        ((33, 34), "."),
												        ((0, 0), tokenizer_r.sep_token),
												    ]
												    if not do_lower_case
												    else [
												        ((0, 0), tokenizer_r.cls_token),
												        ((0, 1), "a"),
												        ((1, 2), ","),
												        ((3, 8), "naive"),
												        ((9, 15), tokenizer_r.mask_token),
												        ((16, 21), "allen"),
												        ((21, 23), "##nl"),
												        ((23, 24), "##p"),
												        ((25, 33), "sentence"),
												        ((33, 34), "."),
												        ((0, 0), tokenizer_r.sep_token),
												    ]
												)

												self.assertEqual(
												    [e[1] for e in expected_results]		,				tokenizer_r.convert_ids_to_tokens(tokens["input_ids"]				)				)
												self.assertEqual([e[0] for e in expected_results]		,				tokens["offset_mapping"]				)






						def       _lowerCAmelCase       (	self				) ->				Optional[int]:
								snake_case_				:							Union[str, Any]						 =       ["的", "人", "有"]
								snake_case_				:							int						 =       "".join(_SCREAMING_SNAKE_CASE				)
								for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
										with self.subTest(f'''{tokenizer.__class__.__name__} ({pretrained_name})'''				):
												snake_case_				:							int						 =       True
												snake_case_				:							Union[str, Any]						 =       self.tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE		,				**_SCREAMING_SNAKE_CASE				)
												snake_case_				:							int						 =       self.rust_tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE		,				**_SCREAMING_SNAKE_CASE				)

												snake_case_				:							List[str]						 =       tokenizer_p.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
												snake_case_				:							Union[str, Any]						 =       tokenizer_r.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)

												snake_case_				:							Tuple						 =       tokenizer_r.convert_ids_to_tokens(_SCREAMING_SNAKE_CASE				)
												snake_case_				:							int						 =       tokenizer_p.convert_ids_to_tokens(_SCREAMING_SNAKE_CASE				)

												# it is expected that each Chinese character is not preceded by "##"
												self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)
												self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)

												snake_case_				:							Optional[int]						 =       False
												snake_case_				:							Dict						 =       self.rust_tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE		,				**_SCREAMING_SNAKE_CASE				)
												snake_case_				:							List[Any]						 =       self.tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE		,				**_SCREAMING_SNAKE_CASE				)

												snake_case_				:							str						 =       tokenizer_r.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)
												snake_case_				:							Any						 =       tokenizer_p.encode(_SCREAMING_SNAKE_CASE		,				add_special_tokens=_SCREAMING_SNAKE_CASE				)

												snake_case_				:							Any						 =       tokenizer_r.convert_ids_to_tokens(_SCREAMING_SNAKE_CASE				)
												snake_case_				:							Any						 =       tokenizer_p.convert_ids_to_tokens(_SCREAMING_SNAKE_CASE				)

												# it is expected that only the first Chinese character is not preceded by "##".
												snake_case_				:							int						 =       [
												    f'''##{token}''' if idx != 0 else token for idx, token in enumerate(_SCREAMING_SNAKE_CASE				)
												]
												self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)
												self.assertListEqual(_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				)
