




"""simple docstring"""


from collections import deque


def       UpperCAmelCase__ (snake_case__							:      Optional[int]					):
  """simple docstring"""

  _snake_case							:	Dict			=						len(snake_case__					)
  _snake_case							:	List[Any]			=						deque()
  _snake_case							:	List[str]			=						[False for _ in range(snake_case__					)]
  _snake_case							:	List[str]			=						[-1 for _ in range(snake_case__					)]
  _snake_case							:	Optional[int]			=						index_of[:]

  def strong_connect(snake_case__							:      List[Any]	,     snake_case__							:      Optional[Any]	,     snake_case__							:      Optional[int]					):
    _snake_case							:	Dict			=						index  # the number when this node is seen
    _snake_case							:	Tuple			=						index  # lowest rank node reachable from here
    index += 1
    stack.append(snake_case__					)
    _snake_case							:	Tuple			=						True

    for w in g[v]:
      if index_of[w] == -1:
        _snake_case							:	int			=						strong_connect(snake_case__	,     snake_case__	,     snake_case__					)
        _snake_case							:	Dict			=						(
            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
        )
      elif on_stack[w]:
        _snake_case							:	Dict			=						(
            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
        )

    if lowlink_of[v] == index_of[v]:
      _snake_case							:	int			=						[]
      _snake_case							:	List[str]			=						stack.pop()
      _snake_case							:	int			=						False
      component.append(snake_case__					)
      while w != v:
        _snake_case							:	Optional[int]			=						stack.pop()
        _snake_case							:	str			=						False
        component.append(snake_case__					)
      components.append(snake_case__					)
    return index

  _snake_case							:	Any			=						[]
  for v in range(snake_case__					):
    if index_of[v] == -1:
      strong_connect(snake_case__	,     0	,     snake_case__					)

  return components


def       UpperCAmelCase__ (snake_case__							:      Optional[int]	,     snake_case__							:      Union[str, Any]					):
  """simple docstring"""

  _snake_case							:	Dict			=						[[] for _ in range(snake_case__					)]
  for u, v in edges:
    g[u].append(snake_case__					)
  return g


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

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








"""simple docstring"""


def       UpperCAmelCase__ (snake_case__							:      int					):
  """simple docstring"""

  if not isinstance(snake_case__	,     snake_case__					) or number < 0:
    raise ValueError("""Input must be a non-negative integer"""					)

  _snake_case							:	Dict			=						0
  while number:
    # This way we arrive at next set bit (next 1) instead of looping
    # through each bit and checking for 1s hence the
    # loop won't run 32 times it will only run the number of `1` times
    number &= number - 1
    count += 1
  return count


if __name__ == "__main__":
     import doctest

     doctest.testmod()


