code: 
  
  
  
  
  
  
  from __future__ import annotations
  
  from queue import Queue
  
  
  
  def 							_lowerCamelCase(				__snake_case						,						__snake_case	)  ->   tuple[int, int]:
  		a ^= b
  		b ^= a
  		a ^= b
  		return a, b
  
  
  
  def 							_lowerCamelCase(				__snake_case						,						__snake_case	)  ->   list[list[int]]:
  		__snake_case		       =     1
  		while (1 << j) < max_node:
  				for i in range(1						,						max_node + 1	):
  						__snake_case		       =     parent[j - 1][parent[j - 1][i]]
  				j += 1
  		return parent
  
  
  
  def 							_lowerCamelCase(				__snake_case						,						__snake_case						,						__snake_case						,						__snake_case	)  ->   int:
  		# u must be deeper in the tree than v
  		if level[u] < level[v]:
  				__snake_case		       =     swap(snake_case__						,						snake_case__	)
  		# making depth of u same as depth of v
  		for i in range(18						,						-1						,						-1	):
  				if level[u] - (1 << i) >= level[v]:
  						__snake_case		       =     parent[i][u]
      # at the same depth if u==v that mean lca is found
  		if u == v:
  				return u
  		# moving both nodes upwards till lca in found
  		for i in range(18						,						-1						,						-1	):
  				if parent[i][u] not in [0, parent[i][v]]:
  						__snake_case		       =     parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
  		return parent[0][u]
  
  
  
  def 							_lowerCamelCase(				__snake_case						,						__snake_case						,						__snake_case						,						__snake_case						,						__snake_case = 1						,						)  ->   tuple[list[int], list[list[int]]]:
  		__snake_case		       =     0
  		__snake_case		       =     Queue(maxsize=snake_case__	)
  		q.put(snake_case__	)
  		while q.qsize() != 0:
  				__snake_case		       =     q.get()
  				for v in graph[u]:
  						if level[v] == -1:
  								__snake_case		       =     level[u] + 1
  								q.put(snake_case__	)
  								__snake_case		       =     u
  		return level, parent
  
  
  
  def 							_lowerCamelCase(				)  ->   None:
  		__snake_case		       =     13
  		# initializing with 0
  		__snake_case		       =     [[0 for _ in range(max_node + 10	)] for _ in range(20	)]
  		# initializing with -1 which means every node is unvisited
  		__snake_case		       =     [-1 for _ in range(max_node + 10	)]
  		__snake_case		       =     {
  		    1: [2, 3, 4],
  		    2: [5],
  		    3: [6, 7],
  		    4: [8],
  		    5: [9, 10],
  		    6: [11],
  		    7: [],
  		    8: [12, 13],
  		    9: [],
  		    10: [],
  		    11: [],
  		    12: [],
  		    13: [],
  		}
  		__snake_case		       =     breadth_first_search(snake_case__						,						snake_case__						,						snake_case__						,						snake_case__						,						1	)
  		__snake_case		       =     create_sparse(snake_case__						,						snake_case__	)
  		print("LCA of node 1 and 3 is: "						,						lowest_common_ancestor(1						,						3						,						snake_case__						,						snake_case__	)	)
  		print("LCA of node 5 and 6 is: "						,						lowest_common_ancestor(5						,						6						,						snake_case__						,						snake_case__	)	)
  		print("LCA of node 7 and 11 is: "						,						lowest_common_ancestor(7						,						11						,						snake_case__						,						snake_case__	)	)
  		print("LCA of node 6 and 7 is: "						,						lowest_common_ancestor(6						,						7						,						snake_case__						,						snake_case__	)	)
  		print("LCA of node 4 and 12 is: "						,						lowest_common_ancestor(4						,						12						,						snake_case__						,						snake_case__	)	)
  		print("LCA of node 8 and 8 is: "						,						lowest_common_ancestor(8						,						8						,						snake_case__						,						snake_case__	)	)
  
  
  if __name__ == "__main__":
  		main()
  
  
  
  
  
  
style_context: import os
  from shutil import copyfile
  from typing import Optional, Tuple
  
  from ...tokenization_utils_fast import PreTrainedTokenizerFast
  from ...utils import is_sentencepiece_available, logging
  
  
  if is_sentencepiece_available():
  		from .tokenization_reformer import ReformerTokenizer
  else:
  		lowerCamelCase__           =				None
  
  
  lowerCamelCase__           =				logging.get_logger(__name__)
  
  
  lowerCamelCase__           =				'▁'
  
  lowerCamelCase__           =				{'vocab_file': 'spiece.model', 'tokenizer_file': 'tokenizer.json'}
  
  lowerCamelCase__           =				{
      'vocab_file': {
          'google/reformer-crime-and-punishment': (
              'https://huggingface.co/google/reformer-crime-and-punishment/resolve/main/spiece.model'
          )
      },
      'tokenizer_file': {
          'google/reformer-crime-and-punishment': (
              'https://huggingface.co/google/reformer-crime-and-punishment/resolve/main/tokenizer.json'
          )
      },
  }
  
  lowerCamelCase__           =				{
      'google/reformer-crime-and-punishment': 52_42_88,
  }
  
  
  
  
  class 					UpperCamelCase	(     snake_case__      ):
  					__UpperCamelCase						=   VOCAB_FILES_NAMES
  					__UpperCamelCase						=   PRETRAINED_VOCAB_FILES_MAP
  					__UpperCamelCase						=   PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
  					__UpperCamelCase						=   ["""input_ids""", """attention_mask"""]
  					__UpperCamelCase						=   ReformerTokenizer
  
  
  
  
  					def __init__( self :					Tuple      ,_lowerCAmelCase :					Dict=None      ,_lowerCAmelCase :					Union[str, Any]=None      ,_lowerCAmelCase :					int="</s>"      ,_lowerCAmelCase :					Dict="<unk>"      ,_lowerCAmelCase :					Dict=[]      ,**_lowerCAmelCase :					Optional[Any]      ,):
  
  
  							"""simple docstring"""
  
  
  
  
  							super().__init__(
  							    _lowerCAmelCase      ,tokenizer_file=_lowerCAmelCase      ,eos_token=_lowerCAmelCase      ,unk_token=_lowerCAmelCase      ,additional_special_tokens=_lowerCAmelCase      ,**_lowerCAmelCase      ,)
  
  							__snake_case		       =     vocab_file
  							__snake_case		       =     False if not self.vocab_file else True
  
  
  
  
  
  
  
  					def 							UpperCamelCase_						( self :					Dict      ,_lowerCAmelCase :					str      ,_lowerCAmelCase :					Optional[str] = None						):
  
  
  							"""simple docstring"""
  
  
  
  
  							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(_lowerCAmelCase						):
  									logger.error(F"""Vocabulary path ({save_directory}) should be a directory"""						)
  									return
  							__snake_case		       =     os.path.join(
  							    _lowerCAmelCase      ,(filename_prefix + "-" if filename_prefix else "") + VOCAB_FILES_NAMES["vocab_file"]						)
  
  							if os.path.abspath(self.vocab_file						) != os.path.abspath(_lowerCAmelCase						):
  									copyfile(self.vocab_file      ,_lowerCAmelCase						)
  
  							return (out_vocab_file,)
  
  
  
  
  
  