



'''simple docstring'''

from math import ceil






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[int]    ,	_SCREAMING_SNAKE_CASE      :int       ):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= list(range(0    ,	_SCREAMING_SNAKE_CASE       )       )

				SCREAMING_SNAKE_CASE  :						List[Any]      					= [item for sublist in list(device_map.values()       ) for item in sublist]

				# Duplicate check
				SCREAMING_SNAKE_CASE  :						Dict      					= []
				for i in device_map_blocks:
								if device_map_blocks.count(_SCREAMING_SNAKE_CASE       ) > 1 and i not in duplicate_blocks:
												duplicate_blocks.append(_SCREAMING_SNAKE_CASE       )
    # Missing blocks
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= [i for i in blocks if i not in device_map_blocks]
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [i for i in device_map_blocks if i not in blocks]

				if len(_SCREAMING_SNAKE_CASE       ) != 0:
								raise ValueError(
								    '''Duplicate attention blocks specified in device_map. Attention blocks must be specified to one device.'''
								    ''' These attention blocks were specified more than once: ''' + str(_SCREAMING_SNAKE_CASE       )       )
				if len(_SCREAMING_SNAKE_CASE       ) != 0:
								raise ValueError(
								    '''There are attention blocks for this model that are not specified in the device_map. Add these attention '''
								    '''blocks to a device on the device_map: ''' + str(_SCREAMING_SNAKE_CASE       )       )
				if len(_SCREAMING_SNAKE_CASE       ) != 0:
								raise ValueError(
								    '''The device_map contains more attention blocks than this model has. Remove these from the device_map:'''
								    + str(_SCREAMING_SNAKE_CASE       )       )






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]       ):
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= list(range(_SCREAMING_SNAKE_CASE       )       )
				SCREAMING_SNAKE_CASE  :						int      					= int(ceil(n_layers / len(_SCREAMING_SNAKE_CASE       )       )       )
				SCREAMING_SNAKE_CASE  :						List[str]      					= [layers[i : i + n_blocks] for i in range(0    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )]

				return dict(zip(_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)




