




from collections import deque


def     lowercase		(  _lowerCAmelCase   ):
  UpperCAmelCase__         = len(UpperCamelCase__   )
  UpperCAmelCase__         = deque()
  UpperCAmelCase__         = [False for _ in range(UpperCamelCase__   )]
  UpperCAmelCase__         = [-1 for _ in range(UpperCamelCase__   )]
  UpperCAmelCase__         = index_of[:]

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

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

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

  return components


def     lowercase		(  _lowerCAmelCase ,  _lowerCAmelCase   ):
  UpperCAmelCase__         = [[] for _ in range(UpperCamelCase__   )]
  for u, v in edges:
    g[u].append(UpperCamelCase__   )
  return g


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

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





'''simple docstring'''




import timeit

import numpy as np

import datasets
from datasets.arrow_writer import ArrowWriter
from datasets.features.features import _ArrayXD






def __lowerCAmelCase					(				UpperCamelCase__							)      ->       List[str]:
    def wrapper(*UpperCamelCase__							,    **UpperCamelCase__							):
        __lowerCamelCase            =    timeit.default_timer()
        __lowerCamelCase            =    func(*UpperCamelCase__							,    **UpperCamelCase__							)
        __lowerCamelCase            =    timeit.default_timer() - starttime
        return delta

    __lowerCamelCase            =    func.__name__

    return wrapper






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__=1_00							,    UpperCamelCase__=None							)      ->       Dict:
    __lowerCamelCase            =    []
    __lowerCamelCase            =    seq_shapes or {}
    for i in range(UpperCamelCase__							):
        __lowerCamelCase            =    {}
        for col_id, (k, v) in enumerate(features.items()							):
            if isinstance(UpperCamelCase__							,    _ArrayXD							):
                __lowerCamelCase            =    np.random.rand(*v.shape							).astype(v.dtype							)
            elif isinstance(UpperCamelCase__							,    datasets.Value							):
                if v.dtype == "string":
                    __lowerCamelCase            =    '''The small grey turtle was surprisingly fast when challenged.'''
                else:
                    __lowerCamelCase            =    np.random.randint(10							,    size=1							).astype(v.dtype							).item()
            elif isinstance(UpperCamelCase__							,    datasets.Sequence							):
                while isinstance(UpperCamelCase__							,    datasets.Sequence							):
                    __lowerCamelCase            =    v.feature
                __lowerCamelCase            =    seq_shapes[k]
                __lowerCamelCase            =    np.random.rand(*UpperCamelCase__							).astype(v.dtype							)
            __lowerCamelCase            =    data

        dummy_data.append((i, example)							)

    return dummy_data






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__=1_00							,    UpperCamelCase__=None							)      ->       Dict:
    __lowerCamelCase            =    generate_examples(UpperCamelCase__							,    num_examples=UpperCamelCase__							,    seq_shapes=UpperCamelCase__							)

    with ArrowWriter(features=UpperCamelCase__							,    path=UpperCamelCase__							) as writer:
        for key, record in dummy_data:
            __lowerCamelCase            =    features.encode_example(UpperCamelCase__							)
            writer.write(UpperCamelCase__							)

        __lowerCamelCase      ,    __lowerCamelCase            =    writer.finalize()

    if not num_final_examples == num_examples:
        raise ValueError(
            f"""Error writing the dataset, wrote {num_final_examples} examples but should have written {num_examples}."""							)

    __lowerCamelCase            =    datasets.Dataset.from_file(filename=UpperCamelCase__							,    info=datasets.DatasetInfo(features=UpperCamelCase__							)							)

    return dataset
