
from collections import deque

def  __lowerCamelCase					( _lowercase			)       ->      Optional[int]:
     UpperCamelCase						    =					len(_lowercase			)
     UpperCamelCase						    =					deque()
     UpperCamelCase						    =					[False for _ in range(_lowercase			)]
     UpperCamelCase						    =					[-1 for _ in range(_lowercase			)]
     UpperCamelCase						    =					index_of[:]

     def strong_connect(_lowercase						,     _lowercase						,     _lowercase			):
          UpperCamelCase						    =					index  # the number when this node is seen
          UpperCamelCase						    =					index  # lowest rank node reachable from here
          index += 1
          stack.append(_lowercase			)
          UpperCamelCase						    =					True

          for w in g[v]:
               if index_of[w] == -1:
                    UpperCamelCase						    =					strong_connect(_lowercase						,     _lowercase						,     _lowercase			)
                    UpperCamelCase						    =					(
                        lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                    )
               elif on_stack[w]:
                    UpperCamelCase						    =					(
                        lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                    )

          if lowlink_of[v] == index_of[v]:
               UpperCamelCase						    =					[]
               UpperCamelCase						    =					stack.pop()
               UpperCamelCase						    =					False
               component.append(_lowercase			)
               while w != v:
                    UpperCamelCase						    =					stack.pop()
                    UpperCamelCase						    =					False
                    component.append(_lowercase			)
               components.append(_lowercase			)
          return index

     UpperCamelCase						    =					[]
     for v in range(_lowercase			):
          if index_of[v] == -1:
               strong_connect(_lowercase						,     0						,     _lowercase			)

     return components

def  __lowerCamelCase					( _lowercase						,     _lowercase			)       ->      List[Any]:
     UpperCamelCase						    =					[[] for _ in range(_lowercase			)]
     for u, v in edges:
          g[u].append(_lowercase			)
     return g


if __name__ == "__main__":
 # Test
 _snake_case      = 7
 _snake_case      = [0, 0, 1, 2, 3, 3, 4, 4, 6]
 _snake_case      = [1, 3, 2, 0, 1, 4, 5, 6, 5]
 _snake_case      = [(u, v) for u, v in zip(source, target)]
 _snake_case      = create_graph(n_vertices, edges)

 assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)




def  __lowerCamelCase					( _lowercase			)       ->      list:
     UpperCamelCase						    =					len(_lowercase			)
     for _ in range(_lowercase			):
          for i in range(_ % 2						,     arr_size - 1						,     2			):
               if arr[i + 1] < arr[i]:
                    UpperCamelCase    ,		UpperCamelCase						    =					arr[i + 1], arr[i]

     return arr


if __name__ == "__main__":
 _snake_case      = list(range(10, 0, -1))
 print(F"Original: {arr}. Sorted: {odd_even_transposition(arr)}")


