





'''simple docstring'''







def  _lowerCamelCase				( lowercase						:      List[str]						)	->	List[str]:
				return [
				    {
				        0: [1, 2],
				        1: [0, 2],
				        2: [0, 1, 3, 5],
				        3: [2, 4],
				        4: [3],
				        5: [2, 6, 8],
				        6: [5, 7],
				        7: [6, 8],
				        8: [5, 7],
				    },
				    {
				        0: [6],
				        1: [9],
				        2: [4, 5],
				        3: [4],
				        4: [2, 3],
				        5: [2],
				        6: [0, 7],
				        7: [6],
				        8: [],
				        9: [1],
				    },
				    {
				        0: [4],
				        1: [6],
				        2: [],
				        3: [5, 6, 7],
				        4: [0, 6],
				        5: [3, 8, 9],
				        6: [1, 3, 4, 7],
				        7: [3, 6, 8, 9],
				        8: [5, 7],
				        9: [5, 7],
				    },
				    {
				        0: [1, 3],
				        1: [0, 2, 4],
				        2: [1, 3, 4],
				        3: [0, 2, 4],
				        4: [1, 2, 3],
				    },
				][index]






def  _lowerCamelCase				( lowercase						:      dict[int, list[int]]						)	->	list[tuple[int, int]]:
				_a								= 0
				_a								= len(lowercase						)  # No of vertices in graph
				_a								= [0] * n
				_a								= [False] * n

				def dfs(lowercase						:      Optional[Any]    ,							lowercase						:      int    ,							lowercase						:      Optional[Any]    ,							lowercase						:      Optional[Any]						):
								_a								= True
								_a								= id_
								id_ += 1
								for to in graph[at]:
												if to == parent:
																pass
												elif not visited[to]:
																dfs(lowercase    ,							lowercase    ,							lowercase    ,							id_						)
																_a								= min(low[at]    ,							low[to]						)
																if id_ <= low[to]:
																				bridges.append((at, to) if at < to else (to, at)						)
												else:
																# This edge is a back edge and cannot be a bridge
																_a								= min(low[at]    ,							low[to]						)

				_a								= []
				for i in range(lowercase						):
								if not visited[i]:
												dfs(lowercase    ,							-1    ,							lowercase    ,							id_						)
				return bridges


if __name__ == "__main__":
					import doctest

					doctest.testmod()

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 		a__						(					unittest.TestCase					):

					def 				__UpperCamelCase   (    self      :       List[str]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		Dict				      =    {
							    "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_  :		Any				      =    {
							    "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      :       str    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		Dict				      =    np.random.randn(3,4    )
							self.assertTrue(np.allclose(transpose(_A    ),x.transpose()    )    )

							SCREAMING_SNAKE_CASE_  :		Tuple				      =    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      :       List[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[str]				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		Any				      =    torch.tensor(_A    )
							self.assertTrue(np.allclose(transpose(_A    ),transpose(_A    ).numpy()    )    )

							SCREAMING_SNAKE_CASE_  :		Dict				      =    np.random.randn(3,4,5    )
							SCREAMING_SNAKE_CASE_  :		Tuple				      =    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      :       List[str]    ):







							"""simple docstring"""






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

							SCREAMING_SNAKE_CASE_  :		List[str]				      =    np.random.randn(3,4,5    )
							SCREAMING_SNAKE_CASE_  :		Union[str, Any]				      =    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[str]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		str				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		Tuple				      =    jnp.array(_A    )
							self.assertTrue(np.allclose(transpose(_A    ),np.asarray(transpose(_A    )    )    )    )

							SCREAMING_SNAKE_CASE_  :		Union[str, Any]				      =    np.random.randn(3,4,5    )
							SCREAMING_SNAKE_CASE_  :		List[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      :       Dict    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		Tuple				      =    np.random.randn(3,4    )
							self.assertTrue(np.allclose(reshape(_A,(4, 3)    ),np.reshape(_A,(4, 3)    )    )    )

							SCREAMING_SNAKE_CASE_  :		Any				      =    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[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[Any]				      =    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_  :		int				      =    torch.tensor(_A    )
							self.assertTrue(np.allclose(reshape(_A,(12, 5)    ),reshape(_A,(12, 5)    ).numpy()    )    )

					@require_tf
					def 				__UpperCamelCase   (    self      :       Dict    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[Any]				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		Optional[Any]				      =    tf.constant(_A    )
							self.assertTrue(np.allclose(reshape(_A,(4, 3)    ),reshape(_A,(4, 3)    ).numpy()    )    )

							SCREAMING_SNAKE_CASE_  :		int				      =    np.random.randn(3,4,5    )
							SCREAMING_SNAKE_CASE_  :		Any				      =    tf.constant(_A    )
							self.assertTrue(np.allclose(reshape(_A,(12, 5)    ),reshape(_A,(12, 5)    ).numpy()    )    )

					@require_flax
					def 				__UpperCamelCase   (    self      :       Tuple    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[str]				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		int				      =    jnp.array(_A    )
							self.assertTrue(np.allclose(reshape(_A,(4, 3)    ),np.asarray(reshape(_A,(4, 3)    )    )    )    )

							SCREAMING_SNAKE_CASE_  :		Union[str, Any]				      =    np.random.randn(3,4,5    )
							SCREAMING_SNAKE_CASE_  :		Tuple				      =    jnp.array(_A    )
							self.assertTrue(np.allclose(reshape(_A,(12, 5)    ),np.asarray(reshape(_A,(12, 5)    )    )    )    )

					def 				__UpperCamelCase   (    self      :       Optional[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		int				      =    np.random.randn(1,3,4    )
							self.assertTrue(np.allclose(squeeze(_A    ),np.squeeze(_A    )    )    )

							SCREAMING_SNAKE_CASE_  :		Any				      =    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]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[str]				      =    np.random.randn(1,3,4    )
							SCREAMING_SNAKE_CASE_  :		Any				      =    torch.tensor(_A    )
							self.assertTrue(np.allclose(squeeze(_A    ),squeeze(_A    ).numpy()    )    )

							SCREAMING_SNAKE_CASE_  :		Any				      =    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      :       Union[str, Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		str				      =    np.random.randn(1,3,4    )
							SCREAMING_SNAKE_CASE_  :		Union[str, Any]				      =    tf.constant(_A    )
							self.assertTrue(np.allclose(squeeze(_A    ),squeeze(_A    ).numpy()    )    )

							SCREAMING_SNAKE_CASE_  :		Any				      =    np.random.randn(1,4,1,5    )
							SCREAMING_SNAKE_CASE_  :		Optional[int]				      =    tf.constant(_A    )
							self.assertTrue(np.allclose(squeeze(_A,axis=2    ),squeeze(_A,axis=2    ).numpy()    )    )

					@require_flax
					def 				__UpperCamelCase   (    self      :       List[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[Any]				      =    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_  :		str				      =    np.random.randn(1,4,1,5    )
							SCREAMING_SNAKE_CASE_  :		Union[str, Any]				      =    jnp.array(_A    )
							self.assertTrue(np.allclose(squeeze(_A,axis=2    ),np.asarray(squeeze(_A,axis=2    )    )    )    )

					def 				__UpperCamelCase   (    self      :       List[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		Tuple				      =    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      :       Dict    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		Tuple				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		List[Any]				      =    torch.tensor(_A    )
							self.assertTrue(np.allclose(expand_dims(_A,axis=1    ),expand_dims(_A,axis=1    ).numpy()    )    )

					@require_tf
					def 				__UpperCamelCase   (    self      :       Union[str, Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		List[Any]				      =    np.random.randn(3,4    )
							SCREAMING_SNAKE_CASE_  :		Optional[int]				      =    tf.constant(_A    )
							self.assertTrue(np.allclose(expand_dims(_A,axis=1    ),expand_dims(_A,axis=1    ).numpy()    )    )






					@require_flax
					def 				__UpperCamelCase   (    self      :       List[Any]    ):







							"""simple docstring"""






							SCREAMING_SNAKE_CASE_  :		int				      =    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    )    )    )    )
