from __future__ import annotations

from queue import Queue

def   a_					(_lowerCAmelCase  :   int			,	_lowerCAmelCase  :   int       )->				tuple[int, int]:
    a ^= b
    b ^= a
    a ^= b
    return a, b

def   a_					(_lowerCAmelCase  :   int			,	_lowerCAmelCase  :   list[list[int]]       )->				list[list[int]]:
    snake_case:						Tuple         =   1
    while (1 << j) < max_node:
        for i in range(1			,	max_node + 1       ):
            snake_case:						Optional[Any]         =   parent[j - 1][parent[j - 1][i]]
        j += 1
    return parent

def   a_					(_lowerCAmelCase  :   int			,	_lowerCAmelCase  :   int			,	_lowerCAmelCase  :   list[int]			,	_lowerCAmelCase  :   list[list[int]]       )->				int:
    # u must be deeper in the tree than v
    if level[u] < level[v]:
        snake_case    , snake_case:						str         =   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]:
            snake_case:						Optional[int]         =   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]]:
            snake_case    , snake_case:						Optional[Any]         =   parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
    return parent[0][u]

def   a_					(_lowerCAmelCase  :   list[int]			,	_lowerCAmelCase  :   list[list[int]]			,	_lowerCAmelCase  :   int			,	_lowerCAmelCase  :   dict[int, list[int]]			,	_lowerCAmelCase  :   int = 1			,	)->				tuple[list[int], list[list[int]]]:
    snake_case:						Any         =   0
    snake_case:						Queue[int]         =   Queue(maxsize=_lowerCAmelCase       )
    q.put(_lowerCAmelCase       )
    while q.qsize() != 0:
        snake_case:						Union[str, Any]         =   q.get()
        for v in graph[u]:
            if level[v] == -1:
                snake_case:						List[Any]         =   level[u] + 1
                q.put(_lowerCAmelCase       )
                snake_case:						str         =   u
    return level, parent

def   a_					()->				None:
    snake_case:						Any         =   13
    # initializing with 0
    snake_case:						Optional[Any]         =   [[0 for _ in range(max_node + 10       )] for _ in range(20       )]
    # initializing with -1 which means every node is unvisited
    snake_case:						List[str]         =   [-1 for _ in range(max_node + 10       )]
    snake_case:						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: [],
    }
    snake_case    , snake_case:						Optional[int]         =   breadth_first_search(_lowerCAmelCase			,	_lowerCAmelCase			,	_lowerCAmelCase			,	_lowerCAmelCase			,	1       )
    snake_case:						Tuple         =   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()



def   a_					(_lowerCAmelCase  :   str       )->				int:
    snake_case:						List[str]         =   0
    for letter in data:
        snake_case:						int         =   (hash_ << 4) + ord(_lowerCAmelCase       )
        snake_case:						Optional[int]         =   hash_ & 0xf_0_0_0_0_0_0_0
        if x != 0:
            hash_ ^= x >> 24
        hash_ &= ~x
    return hash_


if __name__ == "__main__":
    import doctest

    doctest.testmod()


