code: 
  
  from __future__ import annotations
  
  from queue import Queue
  
  
  
  def 			snake_case__    (					SCREAMING_SNAKE_CASE_	:					int			,  SCREAMING_SNAKE_CASE_	:					int    ):
  
  
  
       '''simple docstring'''
  
  
  
  
  
       a ^= b
       b ^= a
       a ^= b
       return a, b
  
  
  
  def 			snake_case__    (					SCREAMING_SNAKE_CASE_	:					int			,  SCREAMING_SNAKE_CASE_	:					list[list[int]]    ):
  
  
  
       '''simple docstring'''
  
  
  
  
  
       lowercase__					:     str   = 1
       while (1 << j) < max_node:
            for i in range(1			,  max_node + 1    ):
                 lowercase__					:     List[str]   = parent[j - 1][parent[j - 1][i]]
            j += 1
       return parent
  
  
  
  def 			snake_case__    (					SCREAMING_SNAKE_CASE_	:					int			,  SCREAMING_SNAKE_CASE_	:					int			,  SCREAMING_SNAKE_CASE_	:					list[int]			,  SCREAMING_SNAKE_CASE_	:					list[list[int]]    ):
  
  
  
       '''simple docstring'''
  
  
  
  
  
       if level[u] < level[v]:
            lowercase__					:     List[Any]   = 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]:
                 lowercase__					:     Tuple   = 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]]:
                 lowercase__					:     List[Any]   = parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
       return parent[0][u]
  
  
  
  def 			snake_case__    (					SCREAMING_SNAKE_CASE_	:					list[int]			,  SCREAMING_SNAKE_CASE_	:					list[list[int]]			,  SCREAMING_SNAKE_CASE_	:					int			,  SCREAMING_SNAKE_CASE_	:					dict[int, list[int]]			,  SCREAMING_SNAKE_CASE_	:					int = 1			,  ):
  
  
  
       '''simple docstring'''
  
  
  
  
  
       lowercase__					:     Optional[Any]   = 0
       lowercase__					:     Queue[int]   = Queue(maxsize=UpperCamelCase__    )
       q.put(UpperCamelCase__    )
       while q.qsize() != 0:
            lowercase__					:     Tuple   = q.get()
            for v in graph[u]:
                 if level[v] == -1:
                      lowercase__					:     List[str]   = level[u] + 1
                      q.put(UpperCamelCase__    )
                      lowercase__					:     Optional[Any]   = u
       return level, parent
  
  
  
  def 			snake_case__    (					):
  
  
  
       '''simple docstring'''
  
  
  
  
  
       lowercase__					:     Tuple   = 13
       # initializing with 0
       lowercase__					:     Optional[Any]   = [[0 for _ in range(max_node + 10    )] for _ in range(20    )]
       # initializing with -1 which means every node is unvisited
       lowercase__					:     Any   = [-1 for _ in range(max_node + 10    )]
       lowercase__					:     dict[int, list[int]]   = {
           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: [],
       }
       lowercase__					:     Optional[int]   = breadth_first_search(UpperCamelCase__			,  UpperCamelCase__			,  UpperCamelCase__			,  UpperCamelCase__			,  1    )
       lowercase__					:     Dict   = 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()
  
  
style_context: 
  
  from dataclasses import dataclass
  from typing import List, Optional, Union
  
  import numpy as np
  import PIL
  
  from ...utils import BaseOutput, is_invisible_watermark_available, is_torch_available, is_transformers_available
  
  
  @dataclass
  class    SCREAMING_SNAKE_CASE__      (__snake_case  ):
      __lowerCamelCase		: Union[List[PIL.Image.Image], np.ndarray]
  
  
  if is_transformers_available() and is_torch_available() and is_invisible_watermark_available():
         from .pipeline_stable_diffusion_xl import StableDiffusionXLPipeline
         from .pipeline_stable_diffusion_xl_imgaimg import StableDiffusionXLImgaImgPipeline
  
  