from collections import deque




def        lowerCAmelCase_			(					__A							)					->    Optional[Any]:







      '''simple docstring'''


      UpperCAmelCase__								=  len(__A							)
      UpperCAmelCase__								=  deque()
      UpperCAmelCase__								=  [False for _ in range(__A							)]
      UpperCAmelCase__								=  [-1 for _ in range(__A							)]
      UpperCAmelCase__								=  index_of[:]

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

            for w in g[v]:
                  if index_of[w] == -1:
                        UpperCAmelCase__								=  strong_connect(__A,  __A,  __A							)
                        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(__A							)
                  while w != v:
                        UpperCAmelCase__								=  stack.pop()
                        UpperCAmelCase__								=  False
                        component.append(__A							)
                  components.append(__A							)
            return index

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

      return components




def        lowerCAmelCase_			(					__A,  __A							)					->    Optional[int]:







      '''simple docstring'''


      UpperCAmelCase__								=  [[] for _ in range(__A							)]
      for u, v in edges:
            g[u].append(__A							)
      return g


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

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




# Lint as: python3
import itertools
import os
import re


UpperCamelCase__    							= re.compile(R'([A-Z]+)([A-Z][a-z])')
UpperCamelCase__    							= re.compile(R'([a-z\d])([A-Z])')

UpperCamelCase__    							= re.compile(R'(?<!_)_(?!_)')
UpperCamelCase__    							= re.compile(R'(_{2,})')

UpperCamelCase__    							= R'^\w+(\.\w+)*$'

UpperCamelCase__    							= R'<>:/\|?*'




def        lowerCAmelCase_			(					__A							)					->    Dict:







      '''simple docstring'''


      UpperCAmelCase__								=  _uppercase_uppercase_re.sub(r"\1_\2",  __A							)
      UpperCAmelCase__								=  _lowercase_uppercase_re.sub(r"\1_\2",  __A							)
      return name.lower()




def        lowerCAmelCase_			(					__A							)					->    Optional[Any]:







      '''simple docstring'''


      UpperCAmelCase__								=  _single_underscore_re.split(__A							)
      UpperCAmelCase__								=  [_multiple_underscores_re.split(__A							) for n in name]
      return "".join(n.capitalize() for n in itertools.chain.from_iterable(__A							) if n != ""							)




def        lowerCAmelCase_			(					__A							)					->    List[str]:







      '''simple docstring'''


      if os.path.basename(__A							) != name:
            raise ValueError(f"""Should be a dataset name, not a path: {name}"""							)
      return camelcase_to_snakecase(__A							)




def        lowerCAmelCase_			(					__A,  __A							)					->    Optional[int]:







      '''simple docstring'''


      if os.path.basename(__A							) != name:
            raise ValueError(f"""Should be a dataset name, not a path: {name}"""							)
      if not re.match(_split_re,  __A							):
            raise ValueError(f"""Split name should match '{_split_re}'' but got '{split}'."""							)
      return f"""{filename_prefix_for_name(__A							)}-{split}"""




def        lowerCAmelCase_			(					__A,  __A,  __A,  __A=None							)					->    str:







      '''simple docstring'''


      UpperCAmelCase__								=  filename_prefix_for_split(__A,  __A							)
      if filetype_suffix:
            prefix += f""".{filetype_suffix}"""
      UpperCAmelCase__								=  os.path.join(__A,  __A							)
      return f"""{filepath}*"""







def        lowerCAmelCase_			(					__A,  __A,  __A,  __A=None,  __A=None							)					->    Any:







      '''simple docstring'''


      UpperCAmelCase__								=  filename_prefix_for_split(__A,  __A							)
      UpperCAmelCase__								=  os.path.join(__A,  __A							)

      if shard_lengths:
            UpperCAmelCase__								=  len(__A							)
            UpperCAmelCase__								=  [f"""{prefix}-{shard_id:05d}-of-{num_shards:05d}""" for shard_id in range(__A							)]
            if filetype_suffix:
                  UpperCAmelCase__								=  [filename + f""".{filetype_suffix}""" for filename in filenames]
            return filenames
      else:
            UpperCAmelCase__								=  prefix
            if filetype_suffix:
                  filename += f""".{filetype_suffix}"""
            return [filename]



