




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"""







from typing import Dict, List, Optional, Union

import numpy as np

from ...image_processing_utils import BaseImageProcessor, BatchFeature, get_size_dict
from ...image_transforms import (
    get_resize_output_image_size,
    normalize,
    pad,
    rescale,
    resize,
    to_channel_dimension_format,
)
from ...image_utils import (
    IMAGENET_STANDARD_MEAN,
    IMAGENET_STANDARD_STD,
    ChannelDimension,
    ImageInput,
    PILImageResampling,
    get_image_size,
    make_list_of_images,
    to_numpy_array,
    valid_images,
)
from ...utils import TensorType, logging
from ...utils.import_utils import is_vision_available


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


if is_vision_available():
						import PIL


class       _lowercase		( __lowerCamelCase	):
				lowerCamelCase__							=							['pixel_values']

				def __init__(  self							:     str							,     _lowercase							:     bool = True							,     _lowercase							:     Dict[str, int] = None							,     _lowercase							:     PILImageResampling = PILImageResampling.BILINEAR							,     _lowercase							:     bool = True							,     _lowercase							:     bool = False							,     _lowercase							:     bool = True							,     _lowercase							:     bool = True							,     _lowercase							:     Union[int, float] = 1 / 2_5_5							,     _lowercase							:     bool = True							,     _lowercase							:     Optional[Union[float, List[float]]] = None							,     _lowercase							:     Optional[Union[float, List[float]]] = None							,     **_lowercase							:     List[str]							,     ):


										'''simple docstring'''
										super().__init__(**_lowercase  )

										UpperCAmelCase__       						=		size if size is not None else {"""height""": 2_5_6_0, """width""": 1_9_2_0}
										if isinstance(_lowercase							,     (tuple, list)  ):
																# The previous feature extractor size parameter was in (width, height) format
																UpperCAmelCase__       						=		size[::-1]
										UpperCAmelCase__       						=		get_size_dict(_lowercase  )

										UpperCAmelCase__       						=		do_resize
										UpperCAmelCase__       						=		size
										UpperCAmelCase__       						=		resample
										UpperCAmelCase__       						=		do_thumbnail
										UpperCAmelCase__       						=		do_align_long_axis
										UpperCAmelCase__       						=		do_pad
										UpperCAmelCase__       						=		do_rescale
										UpperCAmelCase__       						=		rescale_factor
										UpperCAmelCase__       						=		do_normalize
										UpperCAmelCase__       						=		image_mean if image_mean is not None else IMAGENET_STANDARD_MEAN
										UpperCAmelCase__       						=		image_std if image_std is not None else IMAGENET_STANDARD_STD

				def 							A			(  self							:     str							,     _lowercase							:     np.ndarray							,     _lowercase							:     Dict[str, int]							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None  ):


										'''simple docstring'''
										UpperCAmelCase__						,   UpperCAmelCase__       						=		get_image_size(_lowercase  )
										UpperCAmelCase__						,   UpperCAmelCase__       						=		size["""height"""], size["""width"""]

										if (output_width < output_height and input_width > input_height) or (
										    output_width > output_height and input_width < input_height
										):
																UpperCAmelCase__       						=		np.rotaa(_lowercase							,     3  )

										if data_format is not None:
																UpperCAmelCase__       						=		to_channel_dimension_format(_lowercase							,     _lowercase  )

										return image

				def 							A			(  self							:     Tuple							,     _lowercase							:     np.ndarray							,     _lowercase							:     Dict[str, int]							,     _lowercase							:     bool = False							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None							,     ):


										'''simple docstring'''
										UpperCAmelCase__						,   UpperCAmelCase__       						=		size["""height"""], size["""width"""]
										UpperCAmelCase__						,   UpperCAmelCase__       						=		get_image_size(_lowercase  )

										UpperCAmelCase__       						=		output_width - input_width
										UpperCAmelCase__       						=		output_height - input_height

										if random_padding:
																UpperCAmelCase__       						=		np.random.randint(low=0							,     high=delta_height + 1  )
																UpperCAmelCase__       						=		np.random.randint(low=0							,     high=delta_width + 1  )
										else:
																UpperCAmelCase__       						=		delta_height // 2
																UpperCAmelCase__       						=		delta_width // 2

										UpperCAmelCase__       						=		delta_height - pad_top
										UpperCAmelCase__       						=		delta_width - pad_left

										UpperCAmelCase__       						=		((pad_top, pad_bottom), (pad_left, pad_right))
										return pad(_lowercase							,     _lowercase							,     data_format=_lowercase  )

				def 							A			(  self							:     Union[str, Any]							,     *_lowercase							:     List[str]							,     **_lowercase							:     int  ):


										'''simple docstring'''
										logger.info("""pad is deprecated and will be removed in version 4.27. Please use pad_image instead."""  )
										return self.pad_image(*_lowercase							,     **_lowercase  )

				def 							A			(  self							:     Optional[int]							,     _lowercase							:     np.ndarray							,     _lowercase							:     Dict[str, int]							,     _lowercase							:     PILImageResampling = PILImageResampling.BICUBIC							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None							,     **_lowercase							:     Dict							,     ):


										'''simple docstring'''
										UpperCAmelCase__						,   UpperCAmelCase__       						=		get_image_size(_lowercase  )
										UpperCAmelCase__						,   UpperCAmelCase__       						=		size["""height"""], size["""width"""]

										# We always resize to the smallest of either the input or output size.
										UpperCAmelCase__       						=		min(_lowercase							,     _lowercase  )
										UpperCAmelCase__       						=		min(_lowercase							,     _lowercase  )

										if height == input_height and width == input_width:
																return image

										if input_height > input_width:
																UpperCAmelCase__       						=		int(input_width * height / input_height  )
										elif input_width > input_height:
																UpperCAmelCase__       						=		int(input_height * width / input_width  )

										return resize(
										    _lowercase							,     size=(height, width)							,     resample=_lowercase							,     reducing_gap=2.0							,     data_format=_lowercase							,     **_lowercase  )

				def 							A			(  self							:     List[str]							,     _lowercase							:     np.ndarray							,     _lowercase							:     Dict[str, int]							,     _lowercase							:     PILImageResampling = PILImageResampling.BICUBIC							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None							,     **_lowercase							:     Optional[Any]							,     ):


										'''simple docstring'''
										UpperCAmelCase__       						=		get_size_dict(_lowercase  )
										UpperCAmelCase__       						=		min(size["""height"""]							,     size["""width"""]  )
										UpperCAmelCase__       						=		get_resize_output_image_size(_lowercase							,     size=_lowercase							,     default_to_square=_lowercase  )
										UpperCAmelCase__       						=		resize(_lowercase							,     size=_lowercase							,     resample=_lowercase							,     data_format=_lowercase							,     **_lowercase  )
										return resized_image

				def 							A			(  self							:     int							,     _lowercase							:     np.ndarray							,     _lowercase							:     Union[int, float]							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None							,     **_lowercase							:     Union[str, Any]							,     ):


										'''simple docstring'''
										return rescale(_lowercase							,     scale=_lowercase							,     data_format=_lowercase							,     **_lowercase  )

				def 							A			(  self							:     Optional[int]							,     _lowercase							:     np.ndarray							,     _lowercase							:     Union[float, List[float]]							,     _lowercase							:     Union[float, List[float]]							,     _lowercase							:     Optional[Union[str, ChannelDimension]] = None							,     **_lowercase							:     Tuple							,     ):


										'''simple docstring'''
										return normalize(_lowercase							,     mean=_lowercase							,     std=_lowercase							,     data_format=_lowercase							,     **_lowercase  )

				def 							A			(  self							:     List[str]							,     _lowercase							:     ImageInput							,     _lowercase							:     bool = None							,     _lowercase							:     Dict[str, int] = None							,     _lowercase							:     PILImageResampling = None							,     _lowercase							:     bool = None							,     _lowercase							:     bool = None							,     _lowercase							:     bool = None							,     _lowercase							:     bool = False							,     _lowercase							:     bool = None							,     _lowercase							:     float = None							,     _lowercase							:     bool = None							,     _lowercase							:     Optional[Union[float, List[float]]] = None							,     _lowercase							:     Optional[Union[float, List[float]]] = None							,     _lowercase							:     Optional[Union[str, TensorType]] = None							,     _lowercase							:     Optional[ChannelDimension] = ChannelDimension.FIRST							,     **_lowercase							:     Dict							,     ):


										'''simple docstring'''
										UpperCAmelCase__       						=		do_resize if do_resize is not None else self.do_resize
										UpperCAmelCase__       						=		size if size is not None else self.size
										if isinstance(_lowercase							,     (tuple, list)  ):
																# Previous feature extractor had size in (width, height) format
																UpperCAmelCase__       						=		size[::-1]
										UpperCAmelCase__       						=		get_size_dict(_lowercase  )
										UpperCAmelCase__       						=		resample if resample is not None else self.resample
										UpperCAmelCase__       						=		do_thumbnail if do_thumbnail is not None else self.do_thumbnail
										UpperCAmelCase__       						=		do_align_long_axis if do_align_long_axis is not None else self.do_align_long_axis
										UpperCAmelCase__       						=		do_pad if do_pad is not None else self.do_pad
										UpperCAmelCase__       						=		do_rescale if do_rescale is not None else self.do_rescale
										UpperCAmelCase__       						=		rescale_factor if rescale_factor is not None else self.rescale_factor
										UpperCAmelCase__       						=		do_normalize if do_normalize is not None else self.do_normalize
										UpperCAmelCase__       						=		image_mean if image_mean is not None else self.image_mean
										UpperCAmelCase__       						=		image_std if image_std is not None else self.image_std

										UpperCAmelCase__       						=		make_list_of_images(_lowercase  )

										if not valid_images(_lowercase  ):
																raise ValueError(
																    """Invalid image type. Must be of type PIL.Image.Image, numpy.ndarray, """
																    """torch.Tensor, tf.Tensor or jax.ndarray."""  )

										if do_resize and size is None:
																raise ValueError("""Size must be specified if do_resize is True."""  )

										if do_rescale and rescale_factor is None:
																raise ValueError("""Rescale factor must be specified if do_rescale is True."""  )

										if do_pad and size is None:
																raise ValueError("""Size must be specified if do_pad is True."""  )

										if do_normalize and (image_mean is None or image_std is None):
																raise ValueError("""Image mean and std must be specified if do_normalize is True."""  )

										# All transformations expect numpy arrays.
										UpperCAmelCase__       						=		[to_numpy_array(_lowercase  ) for image in images]

										if do_align_long_axis:
																UpperCAmelCase__       						=		[self.align_long_axis(_lowercase							,     size=_lowercase  ) for image in images]

										if do_resize:
																UpperCAmelCase__       						=		[self.resize(image=_lowercase							,     size=_lowercase							,     resample=_lowercase  ) for image in images]

										if do_thumbnail:
																UpperCAmelCase__       						=		[self.thumbnail(image=_lowercase							,     size=_lowercase  ) for image in images]

										if do_pad:
																UpperCAmelCase__       						=		[self.pad_image(image=_lowercase							,     size=_lowercase							,     random_padding=_lowercase  ) for image in images]

										if do_rescale:
																UpperCAmelCase__       						=		[self.rescale(image=_lowercase							,     scale=_lowercase  ) for image in images]

										if do_normalize:
																UpperCAmelCase__       						=		[self.normalize(image=_lowercase							,     mean=_lowercase							,     std=_lowercase  ) for image in images]

										UpperCAmelCase__       						=		[to_channel_dimension_format(_lowercase							,     _lowercase  ) for image in images]

										UpperCAmelCase__       						=		{"""pixel_values""": images}
										return BatchFeature(data=_lowercase							,     tensor_type=_lowercase  )

