

from __future__ import annotations

from queue import Queue


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       tuple[int, int]:






    '''simple docstring'''
    a ^= b
    b ^= a
    a ^= b
    return a, b


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       list[list[int]]:






    '''simple docstring'''
    __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  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       int:






    '''simple docstring'''





    if level[u] < level[v]:
        __UpperCAmelCase   ,       __UpperCAmelCase			   =     swap(SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ )
    # making depth of u same as depth of v
    for i in range(1_8    ,				-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(1_8    ,				-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  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE = 1    ,				) ->       tuple[list[int], list[list[int]]]:






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


def  __a    (				) ->       None:






    '''simple docstring'''
    __UpperCAmelCase			   =     1_3
    # initializing with 0
    __UpperCAmelCase			   =     [[0 for _ in range(max_node + 1_0 )] for _ in range(2_0 )]
    # initializing with -1 which means every node is unvisited
    __UpperCAmelCase			   =     [-1 for _ in range(max_node + 1_0 )]
    __UpperCAmelCase			   =     {
        1: [2, 3, 4],
        2: [5],
        3: [6, 7],
        4: [8],
        5: [9, 1_0],
        6: [1_1],
        7: [],
        8: [1_2, 1_3],
        9: [],
        1_0: [],
        1_1: [],
        1_2: [],
        1_3: [],
    }
    __UpperCAmelCase   ,       __UpperCAmelCase			   =     breadth_first_search(SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_    ,				1 )
    __UpperCAmelCase			   =     create_sparse(SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ )
    print('''LCA of node 1 and 3 is: '''    ,				lowest_common_ancestor(1    ,				3    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )
    print('''LCA of node 5 and 6 is: '''    ,				lowest_common_ancestor(5    ,				6    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )
    print('''LCA of node 7 and 11 is: '''    ,				lowest_common_ancestor(7    ,				1_1    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )
    print('''LCA of node 6 and 7 is: '''    ,				lowest_common_ancestor(6    ,				7    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )
    print('''LCA of node 4 and 12 is: '''    ,				lowest_common_ancestor(4    ,				1_2    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )
    print('''LCA of node 8 and 8 is: '''    ,				lowest_common_ancestor(8    ,				8    ,				SCREAMING_SNAKE_CASE_    ,				SCREAMING_SNAKE_CASE_ ) )


if __name__ == "__main__":
       main()







from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

A_						:     Optional[int]			  =				{
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       list[str]:






    '''simple docstring'''
    __UpperCAmelCase			   =     {start}
    __UpperCAmelCase			   =     [start]
    __UpperCAmelCase			   =     Queue()
    queue.put(SCREAMING_SNAKE_CASE )
    while not queue.empty():
        __UpperCAmelCase			   =     queue.get()
        for w in graph[v]:
            if w not in explored:
                explored.add(SCREAMING_SNAKE_CASE )
                result.append(SCREAMING_SNAKE_CASE )
                queue.put(SCREAMING_SNAKE_CASE )
    return result


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       list[str]:






    '''simple docstring'''
    __UpperCAmelCase			   =     {start}
    __UpperCAmelCase			   =     [start]
    __UpperCAmelCase			   =     deque([start] )
    while queue:
        __UpperCAmelCase			   =     queue.popleft()
        for child in graph[v]:
            if child not in visited:
                visited.add(SCREAMING_SNAKE_CASE )
                result.append(SCREAMING_SNAKE_CASE )
                queue.append(SCREAMING_SNAKE_CASE )
    return result


def  __a    (				SCREAMING_SNAKE_CASE ) ->       None:






    '''simple docstring'''
    __UpperCAmelCase			   =     f'''from __main__ import G, {name}'''
    __UpperCAmelCase			   =     1_0_0_0_0
    __UpperCAmelCase			   =     timeit(f'''{name}(G, \'A\')'''    ,				setup=SCREAMING_SNAKE_CASE    ,				number=SCREAMING_SNAKE_CASE )
    print(f'''{name:<35} finished {number} runs in {res:.5f} seconds''' )


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       benchmark_function('breadth_first_search')
       benchmark_function('breadth_first_search_with_deque')
       # breadth_first_search                finished 10000 runs in 0.20999 seconds
       # breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds




