






from __future__ import annotations

from queue import Queue






def  UpperCAmelCase__						(    lowerCamelCase	:			int			,lowerCamelCase	:			int    ):
   a ^= b
   b ^= a
   a ^= b
   return a, b






def  UpperCAmelCase__						(    lowerCamelCase	:			int			,lowerCamelCase	:			list[list[int]]    ):
   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__						(    lowerCamelCase	:			int			,lowerCamelCase	:			int			,lowerCamelCase	:			list[int]			,lowerCamelCase	:			list[list[int]]    ):
   # u must be deeper in the tree than v
   if level[u] < level[v]:
      lowerCamelCase				,       lowerCamelCase									=swap(lowerCamelCase			,lowerCamelCase    )
   # 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__						(    lowerCamelCase	:			list[int]			,lowerCamelCase	:			list[list[int]]			,lowerCamelCase	:			int			,lowerCamelCase	:			dict[int, list[int]]			,lowerCamelCase	:			int = 1			,):
   lowerCamelCase									=0
   lowerCamelCase									=Queue(maxsize=lowerCamelCase    )
   q.put(lowerCamelCase    )
   while q.qsize() != 0:
      lowerCamelCase									=q.get()
      for v in graph[u]:
         if level[v] == -1:
            lowerCamelCase									=level[u] + 1
            q.put(lowerCamelCase    )
            lowerCamelCase									=u
   return level, parent






def  UpperCAmelCase__						(    ):
   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(lowerCamelCase			,lowerCamelCase			,lowerCamelCase			,lowerCamelCase			,1    )
   lowerCamelCase									=create_sparse(lowerCamelCase			,lowerCamelCase    )
   print("""LCA of node 1 and 3 is: """			,lowest_common_ancestor(1			,3			,lowerCamelCase			,lowerCamelCase    )    )
   print("""LCA of node 5 and 6 is: """			,lowest_common_ancestor(5			,6			,lowerCamelCase			,lowerCamelCase    )    )
   print("""LCA of node 7 and 11 is: """			,lowest_common_ancestor(7			,11			,lowerCamelCase			,lowerCamelCase    )    )
   print("""LCA of node 6 and 7 is: """			,lowest_common_ancestor(6			,7			,lowerCamelCase			,lowerCamelCase    )    )
   print("""LCA of node 4 and 12 is: """			,lowest_common_ancestor(4			,12			,lowerCamelCase			,lowerCamelCase    )    )
   print("""LCA of node 8 and 8 is: """			,lowest_common_ancestor(8			,8			,lowerCamelCase			,lowerCamelCase    )    )


if __name__ == "__main__":
   main()







import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin


if is_torch_available():
   import torch

if is_vision_available():
   from PIL import Image

   from transformers import SwinaSRImageProcessor
   from transformers.image_transforms import get_image_size


class 		lowerCAmelCase_				(  unittest.TestCase ):





     def __init__(	self							, _UpperCAmelCase							, _UpperCAmelCase=7							, _UpperCAmelCase=3							, _UpperCAmelCase=18							, _UpperCAmelCase=30							, _UpperCAmelCase=400							, _UpperCAmelCase=True							, _UpperCAmelCase=1 / 255							, _UpperCAmelCase=True							, _UpperCAmelCase=8							, )		->				Tuple:
        lowerCamelCase									=parent
        lowerCamelCase									=batch_size
        lowerCamelCase									=num_channels
        lowerCamelCase									=image_size
        lowerCamelCase									=min_resolution
        lowerCamelCase									=max_resolution
        lowerCamelCase									=do_rescale
        lowerCamelCase									=rescale_factor
        lowerCamelCase									=do_pad
        lowerCamelCase									=pad_size





     def 						lowerCamelCase							(	self  )		->				Optional[Any]:
        return {
            "do_rescale": self.do_rescale,
            "rescale_factor": self.rescale_factor,
            "do_pad": self.do_pad,
            "pad_size": self.pad_size,
        }





     def 						lowerCamelCase							(	self							, _UpperCAmelCase=False							, _UpperCAmelCase=False							, _UpperCAmelCase=False  )		->				int:
        assert not (numpify and torchify), "You cannot specify both numpy and PyTorch tensors at the same time"

        if equal_resolution:
           lowerCamelCase									=[]
           for i in range(self.batch_size  ):
              image_inputs.append(
                  np.random.randint(
                      255							, size=(self.num_channels, self.max_resolution, self.max_resolution)							, dtype=np.uinta  )  )
        else:
           lowerCamelCase									=[]
           for i in range(self.batch_size  ):
              lowerCamelCase				,       lowerCamelCase									=np.random.choice(np.arange(self.min_resolution							, self.max_resolution  )							, 2  )
              image_inputs.append(np.random.randint(255							, size=(self.num_channels, width, height)							, dtype=np.uinta  )  )

        if not numpify and not torchify:
           # PIL expects the channel dimension as last dimension
           lowerCamelCase									=[Image.fromarray(np.moveaxis(_UpperCAmelCase							, 0							, -1  )  ) for x in image_inputs]

        if torchify:
           lowerCamelCase									=[torch.from_numpy(_UpperCAmelCase  ) for x in image_inputs]

        return image_inputs




@require_torch
@require_vision
class 		lowerCAmelCase_				(  UpperCamelCase				,     unittest.TestCase ):
     __lowerCamelCase       :    Optional[Any] 	=     SwinaSRImageProcessor if is_vision_available() else None





     def 						lowerCamelCase							(	self  )		->				Dict:
        lowerCamelCase									=SwinaSRImageProcessingTester(self  )





     @property
     def 						lowerCamelCase							(	self  )		->				Any:
        return self.image_processor_tester.prepare_image_processor_dict()





     def 						lowerCamelCase							(	self  )		->				Any:
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_rescale"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """rescale_factor"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_pad"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """pad_size"""  )  )





     def 						lowerCamelCase							(	self  )		->				Any:
        pass





     def 						lowerCamelCase							(	self							, _UpperCAmelCase  )		->				int:
        lowerCamelCase				,       lowerCamelCase									=get_image_size(_UpperCAmelCase  )
        lowerCamelCase									=self.image_processor_tester.pad_size

        lowerCamelCase									=(old_height // size + 1) * size - old_height
        lowerCamelCase									=(old_width // size + 1) * size - old_width
        return old_height + pad_height, old_width + pad_width





     def 						lowerCamelCase							(	self  )		->				Optional[Any]:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random PIL images
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, Image.Image  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        lowerCamelCase				,       lowerCamelCase									=self.calculate_expected_size(np.array(image_inputs[0]  )  )
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                expected_height,
                expected_width,
            )							, )





     def 						lowerCamelCase							(	self  )		->				Any:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random numpy tensors
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase							, numpify=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, np.ndarray  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        lowerCamelCase				,       lowerCamelCase									=self.calculate_expected_size(image_inputs[0]  )
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                expected_height,
                expected_width,
            )							, )





     def 						lowerCamelCase							(	self  )		->				Dict:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random PyTorch tensors
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase							, torchify=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, torch.Tensor  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        lowerCamelCase				,       lowerCamelCase									=self.calculate_expected_size(image_inputs[0]  )
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                expected_height,
                expected_width,
            )							, )