






"""simple docstring"""






from __future__ import annotations

from queue import Queue




def 						_UpperCamelCase			(  A    ,       A			):
			a ^= b
			b ^= a
			a ^= b
			return a, b




def 						_UpperCamelCase			(  A    ,       A			):
			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 						_UpperCamelCase			(  A    ,       A    ,       A    ,       A			):







			if level[u] < level[v]:
						UpperCamelCase_    ,							UpperCamelCase_     =swap(A    ,       A			)
			# 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 						_UpperCamelCase			(  A    ,       A    ,       A    ,       A    ,       A = 1    ,       ):
			UpperCamelCase_     =0
			UpperCamelCase_     =Queue(maxsize=A			)
			q.put(A			)
			while q.qsize() != 0:
						UpperCamelCase_     =q.get()
						for v in graph[u]:
									if level[v] == -1:
												UpperCamelCase_     =level[u] + 1
												q.put(A			)
												UpperCamelCase_     =u
			return level, parent




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


if __name__ == "__main__":
				main()








"""simple docstring"""






import unittest
from dataclasses import dataclass
from typing import List, Union

import numpy as np
import PIL.Image

from diffusers.utils.outputs import BaseOutput
@dataclass
class 						__lowerCAmelCase   (			UpperCAmelCase       ):







  '''simple docstring'''


  __lowerCamelCase       :    Union[List[PIL.Image.Image], np.ndarray]




class 						__lowerCAmelCase   (			unittest.TestCase       ):







  '''simple docstring'''


  def 					UpperCamelCase__   (      self:		Tuple					):
     UpperCamelCase_     =CustomOutput(images=np.random.rand(1				,			3				,			4				,			4					)					)

     # check every way of getting the attribute
     assert isinstance(outputs.images				,			np.ndarray					)
     assert outputs.images.shape == (1, 3, 4, 4)
     assert isinstance(outputs["images"]				,			np.ndarray					)
     assert outputs["images"].shape == (1, 3, 4, 4)
     assert isinstance(outputs[0]				,			np.ndarray					)
     assert outputs[0].shape == (1, 3, 4, 4)

     # test with a non-tensor attribute
     UpperCamelCase_     =CustomOutput(images=[PIL.Image.new("RGB"				,			(4, 4)					)]					)

     # check every way of getting the attribute
     assert isinstance(outputs.images				,			UpperCamelCase_					)
     assert isinstance(outputs.images[0]				,			PIL.Image.Image					)
     assert isinstance(outputs["images"]				,			UpperCamelCase_					)
     assert isinstance(outputs["images"][0]				,			PIL.Image.Image					)
     assert isinstance(outputs[0]				,			UpperCamelCase_					)
     assert isinstance(outputs[0][0]				,			PIL.Image.Image					)





  def 					UpperCamelCase__   (      self:		Optional[int]					):
     # test output reinitialization with a `dict` for compatibility with `accelerate`
     UpperCamelCase_     =CustomOutput({"images": np.random.rand(1				,			3				,			4				,			4					)}					)

     # check every way of getting the attribute
     assert isinstance(outputs.images				,			np.ndarray					)
     assert outputs.images.shape == (1, 3, 4, 4)
     assert isinstance(outputs["images"]				,			np.ndarray					)
     assert outputs["images"].shape == (1, 3, 4, 4)
     assert isinstance(outputs[0]				,			np.ndarray					)
     assert outputs[0].shape == (1, 3, 4, 4)

     # test with a non-tensor attribute
     UpperCamelCase_     =CustomOutput({"images": [PIL.Image.new("RGB"				,			(4, 4)					)]}					)

     # check every way of getting the attribute
     assert isinstance(outputs.images				,			UpperCamelCase_					)
     assert isinstance(outputs.images[0]				,			PIL.Image.Image					)
     assert isinstance(outputs["images"]				,			UpperCamelCase_					)
     assert isinstance(outputs["images"][0]				,			PIL.Image.Image					)
     assert isinstance(outputs[0]				,			UpperCamelCase_					)
     assert isinstance(outputs[0][0]				,			PIL.Image.Image					)
