"""simple docstring"""


from itertools import product







def       UpperCAmelCase					(	UpperCAmelCase = 15      )       ->   int:
     snake_case_       =      0.0
     snake_case_       =      42
     snake_case_       =      42
     snake_case_       =      42
     snake_case_       =      42
     snake_case_       =      42
     snake_case_       =      42

     for series in product(range(2      )		,      repeat=UpperCAmelCase      ):
          snake_case_       =      series.count(1      )
          snake_case_       =      num_turns - num_blue
          if num_red >= num_blue:
               continue
          snake_case_       =      1.0
          for ind, col in enumerate(UpperCAmelCase		,      2      ):
               if col == 0:
                    prob *= (ind - 1) / ind
               else:
                    prob *= 1 / ind

          total_prob += prob

     return int(1 / total_prob      )


if __name__ == "__main__":
    print(F"""{solution() = }""")

"""simple docstring"""


from __future__ import annotations

from queue import Queue







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







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase      )       ->   list[list[int]]:
     snake_case_       =      1
     while (1 << j) < max_node:
          for i in range(1		,      max_node + 1      ):
               snake_case_       =      parent[j - 1][parent[j - 1][i]]
          j += 1
     return parent







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase      )       ->   int:
     # u must be deeper in the tree than v
     if level[u] < level[v]:
          snake_case_ ,			snake_case_       =      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]:
               snake_case_       =      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_       =      parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
     return parent[0][u]







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase = 1		,      )       ->   tuple[list[int], list[list[int]]]:
     snake_case_       =      0
     snake_case_       =      Queue(maxsize=UpperCAmelCase      )
     q.put(UpperCAmelCase      )
     while q.qsize() != 0:
          snake_case_       =      q.get()
          for v in graph[u]:
               if level[v] == -1:
                    snake_case_       =      level[u] + 1
                    q.put(UpperCAmelCase      )
                    snake_case_       =      u
     return level, parent







def       UpperCAmelCase					(	)       ->   None:
     snake_case_       =      13
     # initializing with 0
     snake_case_       =      [[0 for _ in range(max_node + 10      )] for _ in range(20      )]
     # initializing with -1 which means every node is unvisited
     snake_case_       =      [-1 for _ in range(max_node + 10      )]
     snake_case_       =      {
         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_       =      breadth_first_search(UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      1      )
     snake_case_       =      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()

