

"""simple docstring"""



from collections import deque





def  _snake_case     (    UpperCAmelCase_  :					Optional[int]			):
     A__										=  len(UpperCAmelCase_			)
     A__										=  deque()
     A__										=  [False for _ in range(UpperCAmelCase_			)]
     A__										=  [-1 for _ in range(UpperCAmelCase_			)]
     A__										=  index_of[:]

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

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

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

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

     return components





def  _snake_case     (    UpperCAmelCase_  :					List[Any]					,   UpperCAmelCase_  :					Optional[Any]			):
     A__										=  [[] for _ in range(UpperCAmelCase_			)]
     for u, v in edges:
          g[u].append(UpperCAmelCase_			)
     return g


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

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








"""simple docstring"""



import math
import sys





def  _snake_case     (    UpperCAmelCase_  :					int			):
     if number != int(UpperCAmelCase_			):
          raise ValueError("""the value of input must be a natural number"""			)
     if number < 0:
          raise ValueError("""the value of input must not be a negative number"""			)
     if number == 0:
          return 1
     A__										=  [-1] * (number + 1)
     A__										=  0
     for i in range(1					,   number + 1			):
          A__										=  sys.maxsize
          A__										=  int(math.sqrt(UpperCAmelCase_			)			)
          for j in range(1					,   root + 1			):
               A__										=  1 + answers[i - (j**2)]
               A__										=  min(UpperCAmelCase_					,   UpperCAmelCase_			)
          A__										=  answer
     return answers[number]


if __name__ == "__main__":
 import doctest

 doctest.testmod()






