




from __future__ import annotations

from queue import Queue





def      UpperCAmelCase  (						UpperCamelCase__						,			UpperCamelCase__   )     ->     tuple[int, int]:







				'''simple docstring'''


				a ^= b
				b ^= a
				a ^= b
				return a, b





def      UpperCAmelCase  (						UpperCamelCase__						,			UpperCamelCase__   )     ->     list[list[int]]:







				'''simple docstring'''


				__lowerCAmelCase					=  1
				while (1 << j) < max_node:
								for i in range(1						,			max_node + 1   ):
												__lowerCAmelCase					=  parent[j - 1][parent[j - 1][i]]
								j += 1
				return parent





def      UpperCAmelCase  (						UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__   )     ->     int:







				'''simple docstring'''


				if level[u] < level[v]:
								__lowerCAmelCase	,				__lowerCAmelCase					=  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]:
												__lowerCAmelCase					=  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]]:
												__lowerCAmelCase	,				__lowerCAmelCase					=  parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
				return parent[0][u]





def      UpperCAmelCase  (						UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__ = 1						,			)     ->     tuple[list[int], list[list[int]]]:







				'''simple docstring'''


				__lowerCAmelCase					=  0
				__lowerCAmelCase					=  Queue(maxsize=UpperCamelCase__   )
				q.put(UpperCamelCase__   )
				while q.qsize() != 0:
								__lowerCAmelCase					=  q.get()
								for v in graph[u]:
												if level[v] == -1:
																__lowerCAmelCase					=  level[u] + 1
																q.put(UpperCamelCase__   )
																__lowerCAmelCase					=  u
				return level, parent





def      UpperCAmelCase  (						)     ->     None:







				'''simple docstring'''


				__lowerCAmelCase					=  13
				# initializing with 0
				__lowerCAmelCase					=  [[0 for _ in range(max_node + 10   )] for _ in range(20   )]
				# initializing with -1 which means every node is unvisited
				__lowerCAmelCase					=  [-1 for _ in range(max_node + 10   )]
				__lowerCAmelCase					=  {
				    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: [],
				}
				__lowerCAmelCase	,				__lowerCAmelCase					=  breadth_first_search(UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__						,			1   )
				__lowerCAmelCase					=  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()













"""simple docstring"""



import warnings

from ...utils import logging
from .image_processing_vit import ViTImageProcessor


_snake_case							:   Tuple	  =       logging.get_logger(__name__)




class 							__lowercase(							_UpperCamelCase	):






						def __init__(       self     ,    *_SCREAMING_SNAKE_CASE     ,    **_SCREAMING_SNAKE_CASE)      ->	None:




											"""simple docstring"""





											warnings.warn(
											    'The class ViTFeatureExtractor is deprecated and will be removed in version 5 of Transformers. Please'
											    ' use ViTImageProcessor instead.'     ,    _SCREAMING_SNAKE_CASE     ,    )
											super().__init__(*_SCREAMING_SNAKE_CASE     ,    **_SCREAMING_SNAKE_CASE)