


"""simple docstring"""




import os
from shutil import copyfile
from typing import List, Optional, Tuple

from tokenizers import processors

from ...tokenization_utils import AddedToken, BatchEncoding
from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import is_sentencepiece_available, logging


if is_sentencepiece_available():
					from .tokenization_nllb import NllbTokenizer
else:
					__magic_name__						: str    =				None


__magic_name__						: Optional[int]    =				logging.get_logger(__name__)


__magic_name__						: Dict    =				{'vocab_file': 'sentencepiece.bpe.model', 'tokenizer_file': 'tokenizer.json'}

__magic_name__						: Tuple    =				{
    'vocab_file': {
        'facebook/nllb-200-distilled-600M': (
            'https://huggingface.co/facebook/nllb-200-distilled-600M/resolve/main/sentencepiece.bpe.model'
        ),
    },
    'tokenizer_file': {
        'facebook/nllb-200-distilled-600M': (
            'https://huggingface.co/facebook/nllb-200-distilled-600M/resolve/main/tokenizer.json'
        ),
    },
}

__magic_name__						: Optional[Any]    =				{
    'facebook/nllb-large-en-ro': 1_0_2_4,
    'facebook/nllb-200-distilled-600M': 1_0_2_4,
}

# fmt: off
__magic_name__						: str    =				['ace_Arab', 'ace_Latn', 'acm_Arab', 'acq_Arab', 'aeb_Arab', 'afr_Latn', 'ajp_Arab', 'aka_Latn', 'amh_Ethi', 'apc_Arab', 'arb_Arab', 'ars_Arab', 'ary_Arab', 'arz_Arab', 'asm_Beng', 'ast_Latn', 'awa_Deva', 'ayr_Latn', 'azb_Arab', 'azj_Latn', 'bak_Cyrl', 'bam_Latn', 'ban_Latn', 'bel_Cyrl', 'bem_Latn', 'ben_Beng', 'bho_Deva', 'bjn_Arab', 'bjn_Latn', 'bod_Tibt', 'bos_Latn', 'bug_Latn', 'bul_Cyrl', 'cat_Latn', 'ceb_Latn', 'ces_Latn', 'cjk_Latn', 'ckb_Arab', 'crh_Latn', 'cym_Latn', 'dan_Latn', 'deu_Latn', 'dik_Latn', 'dyu_Latn', 'dzo_Tibt', 'ell_Grek', 'eng_Latn', 'epo_Latn', 'est_Latn', 'eus_Latn', 'ewe_Latn', 'fao_Latn', 'pes_Arab', 'fij_Latn', 'fin_Latn', 'fon_Latn', 'fra_Latn', 'fur_Latn', 'fuv_Latn', 'gla_Latn', 'gle_Latn', 'glg_Latn', 'grn_Latn', 'guj_Gujr', 'hat_Latn', 'hau_Latn', 'heb_Hebr', 'hin_Deva', 'hne_Deva', 'hrv_Latn', 'hun_Latn', 'hye_Armn', 'ibo_Latn', 'ilo_Latn', 'ind_Latn', 'isl_Latn', 'ita_Latn', 'jav_Latn', 'jpn_Jpan', 'kab_Latn', 'kac_Latn', 'kam_Latn', 'kan_Knda', 'kas_Arab', 'kas_Deva', 'kat_Geor', 'knc_Arab', 'knc_Latn', 'kaz_Cyrl', 'kbp_Latn', 'kea_Latn', 'khm_Khmr', 'kik_Latn', 'kin_Latn', 'kir_Cyrl', 'kmb_Latn', 'kon_Latn', 'kor_Hang', 'kmr_Latn', 'lao_Laoo', 'lvs_Latn', 'lij_Latn', 'lim_Latn', 'lin_Latn', 'lit_Latn', 'lmo_Latn', 'ltg_Latn', 'ltz_Latn', 'lua_Latn', 'lug_Latn', 'luo_Latn', 'lus_Latn', 'mag_Deva', 'mai_Deva', 'mal_Mlym', 'mar_Deva', 'min_Latn', 'mkd_Cyrl', 'plt_Latn', 'mlt_Latn', 'mni_Beng', 'khk_Cyrl', 'mos_Latn', 'mri_Latn', 'zsm_Latn', 'mya_Mymr', 'nld_Latn', 'nno_Latn', 'nob_Latn', 'npi_Deva', 'nso_Latn', 'nus_Latn', 'nya_Latn', 'oci_Latn', 'gaz_Latn', 'ory_Orya', 'pag_Latn', 'pan_Guru', 'pap_Latn', 'pol_Latn', 'por_Latn', 'prs_Arab', 'pbt_Arab', 'quy_Latn', 'ron_Latn', 'run_Latn', 'rus_Cyrl', 'sag_Latn', 'san_Deva', 'sat_Beng', 'scn_Latn', 'shn_Mymr', 'sin_Sinh', 'slk_Latn', 'slv_Latn', 'smo_Latn', 'sna_Latn', 'snd_Arab', 'som_Latn', 'sot_Latn', 'spa_Latn', 'als_Latn', 'srd_Latn', 'srp_Cyrl', 'ssw_Latn', 'sun_Latn', 'swe_Latn', 'swh_Latn', 'szl_Latn', 'tam_Taml', 'tat_Cyrl', 'tel_Telu', 'tgk_Cyrl', 'tgl_Latn', 'tha_Thai', 'tir_Ethi', 'taq_Latn', 'taq_Tfng', 'tpi_Latn', 'tsn_Latn', 'tso_Latn', 'tuk_Latn', 'tum_Latn', 'tur_Latn', 'twi_Latn', 'tzm_Tfng', 'uig_Arab', 'ukr_Cyrl', 'umb_Latn', 'urd_Arab', 'uzn_Latn', 'vec_Latn', 'vie_Latn', 'war_Latn', 'wol_Latn', 'xho_Latn', 'ydd_Hebr', 'yor_Latn', 'yue_Hant', 'zho_Hans', 'zho_Hant', 'zul_Latn']




class 			__snake_case   (lowerCamelCase  ):
							__a					 =       VOCAB_FILES_NAMES
							__a					 =       PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
							__a					 =       PRETRAINED_VOCAB_FILES_MAP
							__a					 =       ['''input_ids''', '''attention_mask''']
							__a					 =       NllbTokenizer

							__a					 =       []
							__a					 =       []




							def __init__(     self:    Optional[Any]     ,							A_:    Optional[int]=None     ,							A_:    str=None     ,							A_:    Tuple="<s>"     ,							A_:    int="</s>"     ,							A_:    Optional[int]="</s>"     ,							A_:    Union[str, Any]="<s>"     ,							A_:    Optional[int]="<unk>"     ,							A_:    List[Any]="<pad>"     ,							A_:    Optional[Any]="<mask>"     ,							A_:    Optional[Any]=None     ,							A_:    Dict=None     ,							A_:    str=None     ,							A_:    Any=False     ,							**A_:    int     ,							):
										# Mask token behave like a normal word, i.e. include the space before it
										__lowerCamelCase          =      AddedToken(A_     ,							lstrip=A_     ,							rstrip=A_   ) if isinstance(A_     ,							A_   ) else mask_token
										__lowerCamelCase          =      legacy_behaviour
										super().__init__(
										    vocab_file=A_     ,							tokenizer_file=A_     ,							bos_token=A_     ,							eos_token=A_     ,							sep_token=A_     ,							cls_token=A_     ,							unk_token=A_     ,							pad_token=A_     ,							mask_token=A_     ,							src_lang=A_     ,							tgt_lang=A_     ,							additional_special_tokens=A_     ,							legacy_behaviour=A_     ,							**A_     ,							)

										__lowerCamelCase          =      vocab_file
										__lowerCamelCase          =      False if not self.vocab_file else True

										__lowerCamelCase          =      FAIRSEQ_LANGUAGE_CODES.copy()

										if additional_special_tokens is not None:
													# Only add those special tokens if they are not already there.
													_additional_special_tokens.extend(
													    [t for t in additional_special_tokens if t not in _additional_special_tokens]   )

										self.add_special_tokens({"""additional_special_tokens""": _additional_special_tokens}   )
										__lowerCamelCase          =      {
										    lang_code: self.convert_tokens_to_ids(A_   ) for lang_code in FAIRSEQ_LANGUAGE_CODES
										}

										__lowerCamelCase          =      src_lang if src_lang is not None else """eng_Latn"""
										__lowerCamelCase          =      self.convert_tokens_to_ids(self._src_lang   )
										__lowerCamelCase          =      tgt_lang
										self.set_src_lang_special_tokens(self._src_lang   )




							@property
							def   __a   (     self:    Any   ):
										return self._src_lang




							@src_lang.setter
							def   __a   (     self:    Optional[Any]     ,							A_:    str   ):
										__lowerCamelCase          =      new_src_lang
										self.set_src_lang_special_tokens(self._src_lang   )




							def   __a   (     self:    Any     ,							A_:    List[int]     ,							A_:    Optional[List[int]] = None   ):
										if token_ids_a is None:
													return self.prefix_tokens + token_ids_a + self.suffix_tokens
										# We don't expect to process pairs, but leave the pair logic for API consistency
										return self.prefix_tokens + token_ids_a + token_ids_a + self.suffix_tokens




							def   __a   (     self:    Tuple     ,							A_:    List[int]     ,							A_:    Optional[List[int]] = None   ):
										__lowerCamelCase          =      [self.sep_token_id]
										__lowerCamelCase          =      [self.cls_token_id]

										if token_ids_a is None:
													return len(cls + token_ids_a + sep   ) * [0]
										return len(cls + token_ids_a + sep + sep + token_ids_a + sep   ) * [0]




							def   __a   (     self:    Any     ,							A_:    Optional[Any]     ,							A_:    str     ,							A_:    Optional[str]     ,							A_:    Optional[str]     ,							**A_:    Tuple   ):
										if src_lang is None or tgt_lang is None:
													raise ValueError("""Translation requires a `src_lang` and a `tgt_lang` for this model"""   )
										__lowerCamelCase          =      src_lang
										__lowerCamelCase          =      self(A_     ,							add_special_tokens=A_     ,							return_tensors=A_     ,							**A_   )
										__lowerCamelCase          =      self.convert_tokens_to_ids(A_   )
										__lowerCamelCase          =      tgt_lang_id
										return inputs




							def   __a   (     self:    List[Any]     ,							A_:    List[str]     ,							A_:    str = "eng_Latn"     ,							A_:    Optional[List[str]] = None     ,							A_:    str = "fra_Latn"     ,							**A_:    Any     ,							):
										__lowerCamelCase          =      src_lang
										__lowerCamelCase          =      tgt_lang
										return super().prepare_seqaseq_batch(A_     ,							A_     ,							**A_   )




							def   __a   (     self:    Optional[Any]   ):
										return self.set_src_lang_special_tokens(self.src_lang   )




							def   __a   (     self:    Dict   ):
										return self.set_tgt_lang_special_tokens(self.tgt_lang   )




							def   __a   (     self:    Union[str, Any]     ,							A_:    Optional[Any]   ):
										__lowerCamelCase          =      self.convert_tokens_to_ids(A_   )

										if self.legacy_behaviour:
													__lowerCamelCase          =      []
													__lowerCamelCase          =      [self.eos_token_id, self.cur_lang_code]
										else:
													__lowerCamelCase          =      [self.cur_lang_code]
													__lowerCamelCase          =      [self.eos_token_id]

										__lowerCamelCase          =      self.convert_ids_to_tokens(self.prefix_tokens   )
										__lowerCamelCase          =      self.convert_ids_to_tokens(self.suffix_tokens   )

										__lowerCamelCase          =      processors.TemplateProcessing(
										    single=prefix_tokens_str + ["""$A"""] + suffix_tokens_str     ,							pair=prefix_tokens_str + ["""$A""", """$B"""] + suffix_tokens_str     ,							special_tokens=list(zip(prefix_tokens_str + suffix_tokens_str     ,							self.prefix_tokens + self.suffix_tokens   )   )     ,							)




							def   __a   (     self:    int     ,							A_:    str   ):
										__lowerCamelCase          =      self.convert_tokens_to_ids(A_   )
										if self.legacy_behaviour:
													__lowerCamelCase          =      []
													__lowerCamelCase          =      [self.eos_token_id, self.cur_lang_code]
										else:
													__lowerCamelCase          =      [self.cur_lang_code]
													__lowerCamelCase          =      [self.eos_token_id]

										__lowerCamelCase          =      self.convert_ids_to_tokens(self.prefix_tokens   )
										__lowerCamelCase          =      self.convert_ids_to_tokens(self.suffix_tokens   )

										__lowerCamelCase          =      processors.TemplateProcessing(
										    single=prefix_tokens_str + ["""$A"""] + suffix_tokens_str     ,							pair=prefix_tokens_str + ["""$A""", """$B"""] + suffix_tokens_str     ,							special_tokens=list(zip(prefix_tokens_str + suffix_tokens_str     ,							self.prefix_tokens + self.suffix_tokens   )   )     ,							)




							def   __a   (     self:    str     ,							A_:    str     ,							A_:    Optional[str] = None   ):
										if not self.can_save_slow_tokenizer:
													raise ValueError(
													    """Your fast tokenizer does not have the necessary information to save the vocabulary for a slow """
													    """tokenizer."""   )

										if not os.path.isdir(A_   ):
													logger.error(f'Vocabulary path ({save_directory}) should be a directory.'   )
													return
										__lowerCamelCase          =      os.path.join(
										    A_     ,							(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""vocab_file"""]   )

										if os.path.abspath(self.vocab_file   ) != os.path.abspath(A_   ):
													copyfile(self.vocab_file     ,							A_   )

										return (out_vocab_file,)








"""simple docstring"""




from collections import defaultdict





def       a_ (	lowercase__ :int     ):
			__lowerCamelCase          =      1
			__lowerCamelCase          =      True
			for v in tree[start]:
						if v not in visited:
									ret += dfs(lowercase__     )
			if ret % 2 == 0:
						cuts.append(lowercase__     )
			return ret





def       a_ (	):
			dfs(1     )


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




