





from __future__ import annotations

from queue import Queue




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_	)  ->		tuple[int, int]:
       a ^= b
       b ^= a
       a ^= b
       return a, b




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_	)  ->		list[list[int]]:
       UpperCamelCase_ 							=	1
       while (1 << j) < max_node:
              for i in range(1       ,		max_node + 1	):
                     UpperCamelCase_ 							=	parent[j - 1][parent[j - 1][i]]
              j += 1
       return parent




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)  ->		int:
       # u must be deeper in the tree than v
       if level[u] < level[v]:
              UpperCamelCase_							,			UpperCamelCase_ 							=	swap(UpperCamelCase_       ,		UpperCamelCase_	)
       # making depth of u same as depth of v
       for i in range(18       ,		-1       ,		-1	):
              if level[u] - (1 << i) >= level[v]:
                     UpperCamelCase_ 							=	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]]:
                     UpperCamelCase_							,			UpperCamelCase_ 							=	parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
       return parent[0][u]




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_ = 1       ,		)  ->		tuple[list[int], list[list[int]]]:
       UpperCamelCase_ 							=	0
       UpperCamelCase_ 							=	Queue(maxsize=UpperCamelCase_	)
       q.put(UpperCamelCase_	)
       while q.qsize() != 0:
              UpperCamelCase_ 							=	q.get()
              for v in graph[u]:
                     if level[v] == -1:
                            UpperCamelCase_ 							=	level[u] + 1
                            q.put(UpperCamelCase_	)
                            UpperCamelCase_ 							=	u
       return level, parent




def 			lowerCAmelCase_			(				)  ->		None:
       UpperCamelCase_ 							=	13
       # initializing with 0
       UpperCamelCase_ 							=	[[0 for _ in range(max_node + 10	)] for _ in range(20	)]
       # initializing with -1 which means every node is unvisited
       UpperCamelCase_ 							=	[-1 for _ in range(max_node + 10	)]
       UpperCamelCase_ 							=	{
           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: [],
       }
       UpperCamelCase_							,			UpperCamelCase_ 							=	breadth_first_search(UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_       ,		1	)
       UpperCamelCase_ 							=	create_sparse(UpperCamelCase_       ,		UpperCamelCase_	)
       print("LCA of node 1 and 3 is: "       ,		lowest_common_ancestor(1       ,		3       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)
       print("LCA of node 5 and 6 is: "       ,		lowest_common_ancestor(5       ,		6       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)
       print("LCA of node 7 and 11 is: "       ,		lowest_common_ancestor(7       ,		11       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)
       print("LCA of node 6 and 7 is: "       ,		lowest_common_ancestor(6       ,		7       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)
       print("LCA of node 4 and 12 is: "       ,		lowest_common_ancestor(4       ,		12       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)
       print("LCA of node 8 and 8 is: "       ,		lowest_common_ancestor(8       ,		8       ,		UpperCamelCase_       ,		UpperCamelCase_	)	)


if __name__ == "__main__":
     main()








from ...configuration_utils import PretrainedConfig
from ...utils import logging


_UpperCAmelCase										=					logging.get_logger(__name__)

_UpperCAmelCase										=					{
    'bert-base-uncased': 'https://huggingface.co/bert-base-uncased/resolve/main/config.json',
    # QDQBERT models can be loaded from any BERT checkpoint, available at https://huggingface.co/models?filter=bert
}



class 				_UpperCamelCase       (						lowerCAmelCase_  ):
       _UpperCamelCase					:       Union[str, Any]       = '''qdqbert'''

       def __init__(		self:			Union[str, Any]       , _SCREAMING_SNAKE_CASE:			Any=30522       , _SCREAMING_SNAKE_CASE:			List[str]=768       , _SCREAMING_SNAKE_CASE:			int=12       , _SCREAMING_SNAKE_CASE:			List[Any]=12       , _SCREAMING_SNAKE_CASE:			Union[str, Any]=3072       , _SCREAMING_SNAKE_CASE:			List[str]="gelu"       , _SCREAMING_SNAKE_CASE:			List[Any]=0.1       , _SCREAMING_SNAKE_CASE:			List[Any]=0.1       , _SCREAMING_SNAKE_CASE:			Dict=512       , _SCREAMING_SNAKE_CASE:			Union[str, Any]=2       , _SCREAMING_SNAKE_CASE:			int=0.02       , _SCREAMING_SNAKE_CASE:			Union[str, Any]=1e-12       , _SCREAMING_SNAKE_CASE:			str=True       , _SCREAMING_SNAKE_CASE:			Any=1       , _SCREAMING_SNAKE_CASE:			int=0       , _SCREAMING_SNAKE_CASE:			Tuple=2       , **_SCREAMING_SNAKE_CASE:			List[str]       , )							->			Tuple:




              """simple docstring"""


              super().__init__(pad_token_id=_SCREAMING_SNAKE_CASE       , bos_token_id=_SCREAMING_SNAKE_CASE       , eos_token_id=_SCREAMING_SNAKE_CASE       , **_SCREAMING_SNAKE_CASE		)

              UpperCamelCase_ 							=	vocab_size
              UpperCamelCase_ 							=	max_position_embeddings
              UpperCamelCase_ 							=	hidden_size
              UpperCamelCase_ 							=	num_hidden_layers
              UpperCamelCase_ 							=	num_attention_heads
              UpperCamelCase_ 							=	intermediate_size
              UpperCamelCase_ 							=	hidden_act
              UpperCamelCase_ 							=	hidden_dropout_prob
              UpperCamelCase_ 							=	attention_probs_dropout_prob
              UpperCamelCase_ 							=	initializer_range
              UpperCamelCase_ 							=	type_vocab_size
              UpperCamelCase_ 							=	layer_norm_eps
              UpperCamelCase_ 							=	use_cache

