

import unittest

import numpy as np

from transformers.testing_utils import require_flax, require_tf, require_torch
from transformers.utils import (
    expand_dims,
    flatten_dict,
    is_flax_available,
    is_tf_available,
    is_torch_available,
    reshape,
    squeeze,
    transpose,
)


if is_flax_available():
			import jax.numpy as jnp

if is_tf_available():
			import tensorflow as tf

if is_torch_available():
			import torch






class _UpperCamelCase							(							unittest.TestCase      ):
			'''simple docstring'''







			def 							__UpperCamelCase       (	self							:       Tuple		)							->				Tuple:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Optional[Any]    =				{
				    "task_specific_params": {
				        "summarization": {"length_penalty": 1.0, "max_length": 128, "min_length": 12, "num_beams": 4},
				        "summarization_cnn": {"length_penalty": 2.0, "max_length": 142, "min_length": 56, "num_beams": 4},
				        "summarization_xsum": {"length_penalty": 1.0, "max_length": 62, "min_length": 11, "num_beams": 6},
				    }
				}
				SCREAMING_SNAKE_CASE      :					int    =				{
				    "task_specific_params.summarization.length_penalty": 1.0,
				    "task_specific_params.summarization.max_length": 128,
				    "task_specific_params.summarization.min_length": 12,
				    "task_specific_params.summarization.num_beams": 4,
				    "task_specific_params.summarization_cnn.length_penalty": 2.0,
				    "task_specific_params.summarization_cnn.max_length": 142,
				    "task_specific_params.summarization_cnn.min_length": 56,
				    "task_specific_params.summarization_cnn.num_beams": 4,
				    "task_specific_params.summarization_xsum.length_penalty": 1.0,
				    "task_specific_params.summarization_xsum.max_length": 62,
				    "task_specific_params.summarization_xsum.min_length": 11,
				    "task_specific_params.summarization_xsum.num_beams": 6,
				}

				self.assertEqual(flatten_dict(a		)					,					a		)
			def 							__UpperCamelCase       (	self							:       int		)							->				Dict:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					List[Any]    =				np.random.randn(3					,					4		)
				self.assertTrue(np.allclose(transpose(a		)					,					x.transpose()		)		)

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(3					,					4					,					5		)
				self.assertTrue(np.allclose(transpose(a					,					axes=(1, 2, 0)		)					,					x.transpose((1, 2, 0)		)		)		)
			@require_torch
			def 							__UpperCamelCase       (	self							:       Tuple		)							->				Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Optional[Any]    =				torch.tensor(a		)
				self.assertTrue(np.allclose(transpose(a		)					,					transpose(a		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					Optional[int]    =				torch.tensor(a		)
				self.assertTrue(np.allclose(transpose(a					,					axes=(1, 2, 0)		)					,					transpose(a					,					axes=(1, 2, 0)		).numpy()		)		)
			@require_tf
			def 							__UpperCamelCase       (	self							:       Tuple		)							->				int:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Optional[Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Tuple    =				tf.constant(a		)
				self.assertTrue(np.allclose(transpose(a		)					,					transpose(a		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					int    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					Dict    =				tf.constant(a		)
				self.assertTrue(np.allclose(transpose(a					,					axes=(1, 2, 0)		)					,					transpose(a					,					axes=(1, 2, 0)		).numpy()		)		)
			@require_flax
			def 							__UpperCamelCase       (	self							:       List[Any]		)							->				Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					List[Any]    =				jnp.array(a		)
				self.assertTrue(np.allclose(transpose(a		)					,					np.asarray(transpose(a		)		)		)		)

				SCREAMING_SNAKE_CASE      :					List[Any]    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					Any    =				jnp.array(a		)
				self.assertTrue(np.allclose(transpose(a					,					axes=(1, 2, 0)		)					,					np.asarray(transpose(a					,					axes=(1, 2, 0)		)		)		)		)
			def 							__UpperCamelCase       (	self							:       List[Any]		)							->				Tuple:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					List[Any]    =				np.random.randn(3					,					4		)
				self.assertTrue(np.allclose(reshape(a					,					(4, 3)		)					,					np.reshape(a					,					(4, 3)		)		)		)

				SCREAMING_SNAKE_CASE      :					Tuple    =				np.random.randn(3					,					4					,					5		)
				self.assertTrue(np.allclose(reshape(a					,					(12, 5)		)					,					np.reshape(a					,					(12, 5)		)		)		)
			@require_torch
			def 							__UpperCamelCase       (	self							:       Optional[int]		)							->				Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					List[str]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					List[str]    =				torch.tensor(a		)
				self.assertTrue(np.allclose(reshape(a					,					(4, 3)		)					,					reshape(a					,					(4, 3)		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					Dict    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					Any    =				torch.tensor(a		)
				self.assertTrue(np.allclose(reshape(a					,					(12, 5)		)					,					reshape(a					,					(12, 5)		).numpy()		)		)
			@require_tf
			def 							__UpperCamelCase       (	self							:       Any		)							->				Any:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Optional[int]    =				tf.constant(a		)
				self.assertTrue(np.allclose(reshape(a					,					(4, 3)		)					,					reshape(a					,					(4, 3)		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					int    =				tf.constant(a		)
				self.assertTrue(np.allclose(reshape(a					,					(12, 5)		)					,					reshape(a					,					(12, 5)		).numpy()		)		)
			@require_flax
			def 							__UpperCamelCase       (	self							:       Optional[int]		)							->				List[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					List[Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Optional[Any]    =				jnp.array(a		)
				self.assertTrue(np.allclose(reshape(a					,					(4, 3)		)					,					np.asarray(reshape(a					,					(4, 3)		)		)		)		)

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(3					,					4					,					5		)
				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				jnp.array(a		)
				self.assertTrue(np.allclose(reshape(a					,					(12, 5)		)					,					np.asarray(reshape(a					,					(12, 5)		)		)		)		)
			def 							__UpperCamelCase       (	self							:       int		)							->				List[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Dict    =				np.random.randn(1					,					3					,					4		)
				self.assertTrue(np.allclose(squeeze(a		)					,					np.squeeze(a		)		)		)

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(1					,					4					,					1					,					5		)
				self.assertTrue(np.allclose(squeeze(a					,					axis=2		)					,					np.squeeze(a					,					axis=2		)		)		)
			@require_torch
			def 							__UpperCamelCase       (	self							:       List[str]		)							->				Tuple:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(1					,					3					,					4		)
				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				torch.tensor(a		)
				self.assertTrue(np.allclose(squeeze(a		)					,					squeeze(a		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					int    =				np.random.randn(1					,					4					,					1					,					5		)
				SCREAMING_SNAKE_CASE      :					Dict    =				torch.tensor(a		)
				self.assertTrue(np.allclose(squeeze(a					,					axis=2		)					,					squeeze(a					,					axis=2		).numpy()		)		)
			@require_tf
			def 							__UpperCamelCase       (	self							:       Tuple		)							->				Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(1					,					3					,					4		)
				SCREAMING_SNAKE_CASE      :					str    =				tf.constant(a		)
				self.assertTrue(np.allclose(squeeze(a		)					,					squeeze(a		).numpy()		)		)

				SCREAMING_SNAKE_CASE      :					List[str]    =				np.random.randn(1					,					4					,					1					,					5		)
				SCREAMING_SNAKE_CASE      :					Any    =				tf.constant(a		)
				self.assertTrue(np.allclose(squeeze(a					,					axis=2		)					,					squeeze(a					,					axis=2		).numpy()		)		)
			@require_flax
			def 							__UpperCamelCase       (	self							:       int		)							->				Dict:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Dict    =				np.random.randn(1					,					3					,					4		)
				SCREAMING_SNAKE_CASE      :					List[str]    =				jnp.array(a		)
				self.assertTrue(np.allclose(squeeze(a		)					,					np.asarray(squeeze(a		)		)		)		)

				SCREAMING_SNAKE_CASE      :					int    =				np.random.randn(1					,					4					,					1					,					5		)
				SCREAMING_SNAKE_CASE      :					str    =				jnp.array(a		)
				self.assertTrue(np.allclose(squeeze(a					,					axis=2		)					,					np.asarray(squeeze(a					,					axis=2		)		)		)		)
			def 							__UpperCamelCase       (	self							:       str		)							->				List[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					List[str]    =				np.random.randn(3					,					4		)
				self.assertTrue(np.allclose(expand_dims(a					,					axis=1		)					,					np.expand_dims(a					,					axis=1		)		)		)
			@require_torch
			def 							__UpperCamelCase       (	self							:       Optional[int]		)							->				Any:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					str    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Tuple    =				torch.tensor(a		)
				self.assertTrue(np.allclose(expand_dims(a					,					axis=1		)					,					expand_dims(a					,					axis=1		).numpy()		)		)
			@require_tf
			def 							__UpperCamelCase       (	self							:       Optional[int]		)							->				Dict:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Dict    =				tf.constant(a		)
				self.assertTrue(np.allclose(expand_dims(a					,					axis=1		)					,					expand_dims(a					,					axis=1		).numpy()		)		)






			@require_flax
			def 							__UpperCamelCase       (	self							:       Optional[int]		)							->				List[str]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				np.random.randn(3					,					4		)
				SCREAMING_SNAKE_CASE      :					Union[str, Any]    =				jnp.array(a		)
				self.assertTrue(np.allclose(expand_dims(a					,					axis=1		)					,					np.asarray(expand_dims(a					,					axis=1		)		)		)		)

from collections import deque





def 			lowerCamelCase_ (				lowerCamelCase__    ):
				lowerCamelCase_						=			len(lowerCamelCase__    )
				lowerCamelCase_						=			deque()
				lowerCamelCase_						=			[False for _ in range(lowerCamelCase__    )]
				lowerCamelCase_						=			[-1 for _ in range(lowerCamelCase__    )]
				lowerCamelCase_						=			index_of[:]

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

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

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

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

				return components





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__    ):
				lowerCamelCase_						=			[[] for _ in range(lowerCamelCase__    )]
				for u, v in edges:
								g[u].append(lowerCamelCase__    )
				return g


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

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


