
'''simple docstring'''

import importlib.metadata
import operator
import re
import sys
from typing import Optional

from packaging import version


snake_case_			=     {
    """<""": operator.lt,
    """<=""": operator.le,
    """==""": operator.eq,
    """!=""": operator.ne,
    """>=""": operator.ge,
    """>""": operator.gt,
}






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[int]    ,	_SCREAMING_SNAKE_CASE      :Dict    ,	_SCREAMING_SNAKE_CASE      :Optional[int]    ,	_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :Optional[Any]    ,	_SCREAMING_SNAKE_CASE      :List[Any]       ):
				if got_ver is None or want_ver is None:
								raise ValueError(
								    F'''Unable to compare versions for {requirement}: need={want_ver} found={got_ver}. This is unusual. Consider'''
								    F''' reinstalling {pkg}.'''       )
				if not ops[op](version.parse(_SCREAMING_SNAKE_CASE       )    ,	version.parse(_SCREAMING_SNAKE_CASE       )       ):
								raise ImportError(
								    F'''{requirement} is required for a normal functioning of this module, but found {pkg}=={got_ver}.{hint}'''       )






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :Optional[str] = None       ):
				SCREAMING_SNAKE_CASE  :						Any      					= F'''\n{hint}''' if hint is not None else ''''''

				# non-versioned check
				if re.match(R'''^[\w_\-\d]+$'''    ,	_SCREAMING_SNAKE_CASE       ):
								SCREAMING_SNAKE_CASE  :						List[Any]      					= requirement, None, None
				else:
								SCREAMING_SNAKE_CASE  :						int      					= re.findall(R'''^([^!=<>\s]+)([\s!=<>]{1,2}.+)'''    ,	_SCREAMING_SNAKE_CASE       )
								if not match:
												raise ValueError(
												    '''requirement needs to be in the pip package format, .e.g., package_a==1.23, or package_b>=1.23, but'''
												    F''' got {requirement}'''       )
								SCREAMING_SNAKE_CASE  :						Optional[int]      					= match[0]
								SCREAMING_SNAKE_CASE  :						Optional[Any]      					= want_full.split(''','''       )  # there could be multiple requirements
								SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= {}
								for w in want_range:
												SCREAMING_SNAKE_CASE  :						Optional[int]      					= re.findall(R'''^([\s!=<>]{1,2})(.+)'''    ,	_SCREAMING_SNAKE_CASE       )
												if not match:
																raise ValueError(
																    '''requirement needs to be in the pip package format, .e.g., package_a==1.23, or package_b>=1.23,'''
																    F''' but got {requirement}'''       )
												SCREAMING_SNAKE_CASE  :						Tuple      					= match[0]
												SCREAMING_SNAKE_CASE  :						Any      					= want_ver
												if op not in ops:
																raise ValueError(F'''{requirement}: need one of {list(ops.keys()       )}, but got {op}'''       )

    # special case
				if pkg == "python":
								SCREAMING_SNAKE_CASE  :						Optional[int]      					= '''.'''.join([str(_SCREAMING_SNAKE_CASE       ) for x in sys.version_info[:3]]       )
								for op, want_ver in wanted.items():
												_compare_versions(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
								return

				# check if any version is installed
				try:
								SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= importlib.metadata.version(_SCREAMING_SNAKE_CASE       )
				except importlib.metadata.PackageNotFoundError:
								raise importlib.metadata.PackageNotFoundError(
								    F'''The \'{requirement}\' distribution was not found and is required by this application. {hint}'''       )

				# check that the right version is installed if version number or a range was provided
				if want_ver is not None:
								for op, want_ver in wanted.items():
												_compare_versions(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= '''Try: pip install transformers -U or pip install -e \'.[dev]\' if you\'re working with git main'''
				return require_version(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )









'''simple docstring'''

from collections import deque






def       __lowercase  (_SCREAMING_SNAKE_CASE      :List[str]       ):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= len(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						List[str]      					= deque()
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= [False for _ in range(_SCREAMING_SNAKE_CASE       )]
				SCREAMING_SNAKE_CASE  :						Any      					= [-1 for _ in range(_SCREAMING_SNAKE_CASE       )]
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= index_of[:]

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

								for w in g[v]:
												if index_of[w] == -1:
																SCREAMING_SNAKE_CASE  :						List[str]      					= strong_connect(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
																SCREAMING_SNAKE_CASE  :						Optional[int]      					= (
																    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																)
												elif on_stack[w]:
																SCREAMING_SNAKE_CASE  :						List[str]      					= (
																    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																)

								if lowlink_of[v] == index_of[v]:
												SCREAMING_SNAKE_CASE  :						str      					= []
												SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= stack.pop()
												SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= False
												component.append(_SCREAMING_SNAKE_CASE       )
												while w != v:
																SCREAMING_SNAKE_CASE  :						int      					= stack.pop()
																SCREAMING_SNAKE_CASE  :						Tuple      					= False
																component.append(_SCREAMING_SNAKE_CASE       )
												components.append(_SCREAMING_SNAKE_CASE       )
								return index

				SCREAMING_SNAKE_CASE  :						int      					= []
				for v in range(_SCREAMING_SNAKE_CASE       ):
								if index_of[v] == -1:
												strong_connect(_SCREAMING_SNAKE_CASE    ,	0    ,	_SCREAMING_SNAKE_CASE       )

				return components






def       __lowercase  (_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :Optional[int]       ):
				SCREAMING_SNAKE_CASE  :						Tuple      					= [[] for _ in range(_SCREAMING_SNAKE_CASE       )]
				for u, v in edges:
								g[u].append(_SCREAMING_SNAKE_CASE       )
				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)




