from __future__ import annotations

from queue import Queue

def      lowercase_							(     _lowerCamelCase				:			Optional[int]						,      _lowerCamelCase				:			List[str]):
    a ^= b
    b ^= a
    a ^= b
    return a, b

def      lowercase_							(     _lowerCamelCase				:			List[Any]						,      _lowerCamelCase				:			Any):
    lowercase__					:  Optional[Any]          =							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      lowercase_							(     _lowerCamelCase				:			Optional[int]						,      _lowerCamelCase				:			List[str]						,      _lowerCamelCase				:			int						,      _lowerCamelCase				:			Dict):



    if level[u] < level[v]:
        lowercase__   ,  lowercase__					:  int          =							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]:
            lowercase__					:  str          =							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__   ,  lowercase__					:  List[str]          =							parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
    return parent[0][u]

def      lowercase_							(     _lowerCamelCase				:			Optional[int]						,      _lowerCamelCase				:			Optional[Any]						,      _lowerCamelCase				:			int						,      _lowerCamelCase				:			str						,      _lowerCamelCase				:			Any = 1						,      ):
    lowercase__					:  List[str]          =							0
    lowercase__					:  Union[str, Any]          =							Queue(maxsize=__A)
    q.put(__A)
    while q.qsize() != 0:
        lowercase__					:  List[str]          =							q.get()
        for v in graph[u]:
            if level[v] == -1:
                lowercase__					:  Tuple          =							level[u] + 1
                q.put(__A)
                lowercase__					:  Optional[int]          =							u
    return level, parent

def      lowercase_							(     ):
    lowercase__					:  List[str]          =							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__					:  int          =							[-1 for _ in range(max_node + 10)]
    lowercase__					:  Union[str, Any]          =							{
        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__   ,  lowercase__					:  List[str]          =							breadth_first_search(__A						,      __A						,      __A						,      __A						,      1)
    lowercase__					:  Dict          =							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'''







def _UpperCamelCase			(	__A ,     __A       )				->						int:


      '''simple docstring'''



      return (input_a, input_a).count(0       ) % 2







def _UpperCamelCase			(	)				->						None:


      '''simple docstring'''



      assert xor_gate(0 ,     0       ) == 0
      assert xor_gate(0 ,     1       ) == 1
      assert xor_gate(1 ,     0       ) == 1
      assert xor_gate(1 ,     1       ) == 0


if __name__ == "__main__":
  print(xor_gate(0, 0))
  print(xor_gate(0, 1))





