


'''simple docstring'''







from __future__ import annotations

from queue import Queue







def _UpperCamelCase			(	__A ,     __A       )				->						tuple[int, int]:


      '''simple docstring'''



      a ^= b
      b ^= a
      a ^= b
      return a, b







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


      '''simple docstring'''



      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 ,     )				->						tuple[list[int], list[list[int]]]:


      '''simple docstring'''



      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			(	)				->						None:


      '''simple docstring'''



      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'''







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))





