
from collections import deque

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     List[Any]      ):
				"""simple docstring"""







				return input(_SCREAMING_SNAKE_CASE      ).strip().split(""" """      )

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     List[str]			,       _SCREAMING_SNAKE_CASE    :     Union[str, Any]      ):
				"""simple docstring"""







				__a					       =						{}
				for i in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						[]

				for e in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						(int(_SCREAMING_SNAKE_CASE      ) for i in _input(f"Edge {e + 1}: <node1> <node2> "      ))
								graph[x].append(_SCREAMING_SNAKE_CASE      )
				return graph

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Tuple			,       _SCREAMING_SNAKE_CASE    :     Dict      ):
				"""simple docstring"""







				__a					       =						{}
				for i in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						[]

				for e in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						(int(_SCREAMING_SNAKE_CASE      ) for i in _input(f"Edge {e + 1}: <node1> <node2> "      ))
								graph[x].append(_SCREAMING_SNAKE_CASE      )
								graph[y].append(_SCREAMING_SNAKE_CASE      )
				return graph

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     str			,       _SCREAMING_SNAKE_CASE    :     Tuple      ):
				"""simple docstring"""







				__a					       =						{}
				for i in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						[]

				for e in range(_SCREAMING_SNAKE_CASE      ):
								__a					       =						(int(_SCREAMING_SNAKE_CASE      ) for i in _input(f"Edge {e + 1}: <node1> <node2> <weight> "      ))
								graph[x].append((y, w)      )
								graph[y].append((x, w)      )
				return graph


if __name__ == "__main__":
						lowerCamelCase__     =	(int(i) for i in _input("""Number of nodes and edges: """))

						lowerCamelCase__     =	int(
						    _input(
						        """Press 1 or 2 or 3 \n"""
						        """1. Unweighted directed \n"""
						        """2. Unweighted undirected \n"""
						        """3. Weighted undirected \n"""
						    )[0]
						)

						lowerCamelCase__     =	{
						    1: initialize_unweighted_directed_graph,
						    2: initialize_unweighted_undirected_graph,
						    3: initialize_weighted_undirected_graph,
						}[graph_choice](n, m)

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Dict			,       _SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







				__a					       =						{s}, [s]
				print(_SCREAMING_SNAKE_CASE      )
				while _s:
								__a					       =						0
								for i in g[_s[-1]]:
												if i not in vis:
																_s.append(_SCREAMING_SNAKE_CASE      )
																vis.add(_SCREAMING_SNAKE_CASE      )
																__a					       =						1
																print(_SCREAMING_SNAKE_CASE      )
																break
								if not flag:
												_s.pop()

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Tuple			,       _SCREAMING_SNAKE_CASE    :     Tuple      ):
				"""simple docstring"""







				__a					       =						{s}, deque([s]      )
				print(_SCREAMING_SNAKE_CASE      )
				while q:
								__a					       =						q.popleft()
								for v in g[u]:
												if v not in vis:
																vis.add(_SCREAMING_SNAKE_CASE      )
																q.append(_SCREAMING_SNAKE_CASE      )
																print(_SCREAMING_SNAKE_CASE      )

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Union[str, Any]			,       _SCREAMING_SNAKE_CASE    :     List[str]      ):
				"""simple docstring"""







				__a					       =						{s: 0}, set(), {s: 0}
				while True:
								if len(_SCREAMING_SNAKE_CASE      ) == len(_SCREAMING_SNAKE_CASE      ) - 1:
												break
								__a					       =						10_0000
								for i in dist:
												if i not in known and dist[i] < mini:
																__a					       =						dist[i]
																__a					       =						i
								known.add(_SCREAMING_SNAKE_CASE      )
								for v in g[u]:
												if v[0] not in known and dist[u] + v[1] < dist.get(v[0]			,       10_0000      ):
																__a					       =						dist[u] + v[1]
																__a					       =						u
				for i in dist:
								if i != s:
												print(dist[i]      )

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Optional[int]			,       _SCREAMING_SNAKE_CASE    :     Dict=None			,       _SCREAMING_SNAKE_CASE    :     Tuple=None      ):
				"""simple docstring"""







				if q is None:
								__a					       =						[1]
				if ind is None:
								__a					       =						[0] * (len(_SCREAMING_SNAKE_CASE      ) + 1)  # SInce oth Index is ignored
								for u in g:
												for v in g[u]:
																ind[v] += 1
								__a					       =						deque()
								for i in g:
												if ind[i] == 0:
																q.append(_SCREAMING_SNAKE_CASE      )
				if len(_SCREAMING_SNAKE_CASE      ) == 0:
								return
				__a					       =						q.popleft()
				print(_SCREAMING_SNAKE_CASE      )
				for w in g[v]:
								ind[w] -= 1
								if ind[w] == 0:
												q.append(_SCREAMING_SNAKE_CASE      )
				topo(_SCREAMING_SNAKE_CASE			,       _SCREAMING_SNAKE_CASE			,       _SCREAMING_SNAKE_CASE      )

def 					lowerCAmelCase__  (							):
				"""simple docstring"""







				__a					       =						input().strip()
				__a					       =						[]
				for _ in range(_SCREAMING_SNAKE_CASE      ):
								a.append(map(_SCREAMING_SNAKE_CASE			,       input().strip().split()      )      )
				return a, n

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     List[str]      ):
				"""simple docstring"""







				(__a)					       =						a_and_n
				__a					       =						list(_SCREAMING_SNAKE_CASE      )
				__a					       =						[[0] * n for i in range(_SCREAMING_SNAKE_CASE      )]
				for k in range(_SCREAMING_SNAKE_CASE      ):
								for i in range(_SCREAMING_SNAKE_CASE      ):
												for j in range(_SCREAMING_SNAKE_CASE      ):
																if dist[i][j] > dist[i][k] + dist[k][j]:
																				__a					       =						dist[i][k] + dist[k][j]
																				__a					       =						k
				print(_SCREAMING_SNAKE_CASE      )

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Tuple			,       _SCREAMING_SNAKE_CASE    :     int      ):
				"""simple docstring"""







				__a					       =						{s: 0}, set(), {s: 0}
				while True:
								if len(_SCREAMING_SNAKE_CASE      ) == len(_SCREAMING_SNAKE_CASE      ) - 1:
												break
								__a					       =						10_0000
								for i in dist:
												if i not in known and dist[i] < mini:
																__a					       =						dist[i]
																__a					       =						i
								known.add(_SCREAMING_SNAKE_CASE      )
								for v in g[u]:
												if v[0] not in known and v[1] < dist.get(v[0]			,       10_0000      ):
																__a					       =						v[1]
																__a					       =						u
				return dist

def 					lowerCAmelCase__  (							):
				"""simple docstring"""







				__a					       =						map(_SCREAMING_SNAKE_CASE			,       input().split(""" """      )      )
				__a					       =						[]
				for _ in range(_SCREAMING_SNAKE_CASE      ):
								edges.append(map(_SCREAMING_SNAKE_CASE			,       input().split(""" """      )      )      )
				return edges, n

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Dict      ):
				"""simple docstring"""







				(__a)					       =						e_and_n
				e.sort(reverse=_SCREAMING_SNAKE_CASE			,       key=lambda _SCREAMING_SNAKE_CASE      : x[2]      )
				__a					       =						[{i} for i in range(1			,       n + 1      )]
				while True:
								if len(_SCREAMING_SNAKE_CASE      ) == 1:
												break
								print(_SCREAMING_SNAKE_CASE      )
								__a					       =						e.pop()
								for i in range(len(_SCREAMING_SNAKE_CASE      )      ):
												if x[0] in s[i]:
																break
								for j in range(len(_SCREAMING_SNAKE_CASE      )      ):
												if x[1] in s[j]:
																if i == j:
																				break
																s[j].update(s[i]      )
																s.pop(_SCREAMING_SNAKE_CASE      )
																break

def 					lowerCAmelCase__  (							_SCREAMING_SNAKE_CASE    :     Union[str, Any]      ):
				"""simple docstring"""







				__a					       =						[]
				for node in graph:
								if not graph[node]:
												isolated.append(_SCREAMING_SNAKE_CASE      )
				return isolated





import inspect
import unittest

from transformers import ResNetConfig, is_flax_available
from transformers.testing_utils import require_flax, slow
from transformers.utils import cached_property, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_flax_common import FlaxModelTesterMixin, floats_tensor


if is_flax_available():
						import jax
						import jax.numpy as jnp

						from transformers.models.resnet.modeling_flax_resnet import FlaxResNetForImageClassification, FlaxResNetModel

if is_vision_available():
						from PIL import Image

						from transformers import AutoImageProcessor






class 				SCREAMING_SNAKE_CASE     (							unittest.TestCase   ):





							def __init__(				self						:						Optional[int] ,			__lowercase						:						str ,			__lowercase						:						str=3 ,			__lowercase						:						Optional[int]=32 ,			__lowercase						:						Union[str, Any]=3 ,			__lowercase						:						str=10 ,			__lowercase						:						int=[10, 20, 30, 40] ,			__lowercase						:						Any=[1, 1, 2, 1] ,			__lowercase						:						Optional[int]=True ,			__lowercase						:						Optional[int]=True ,			__lowercase						:						int="relu" ,			__lowercase						:						Union[str, Any]=3 ,			__lowercase						:						List[str]=None ,			):

											'''simple docstring'''
											__a					       =						parent
											__a					       =						batch_size
											__a					       =						image_size
											__a					       =						num_channels
											__a					       =						embeddings_size
											__a					       =						hidden_sizes
											__a					       =						depths
											__a					       =						is_training
											__a					       =						use_labels
											__a					       =						hidden_act
											__a					       =						num_labels
											__a					       =						scope
											__a					       =						len(__lowercase		)





							def   UpperCamelCase_   (				self						:						List[Any]		):

											'''simple docstring'''
											__a					       =						floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]		)

											__a					       =						self.get_config()

											return config, pixel_values





							def   UpperCamelCase_   (				self						:						Optional[int]		):

											'''simple docstring'''
											return ResNetConfig(
											    num_channels=self.num_channels ,			embeddings_size=self.embeddings_size ,			hidden_sizes=self.hidden_sizes ,			depths=self.depths ,			hidden_act=self.hidden_act ,			num_labels=self.num_labels ,			image_size=self.image_size ,			)





							def   UpperCamelCase_   (				self						:						List[str] ,			__lowercase						:						Union[str, Any] ,			__lowercase						:						str		):

											'''simple docstring'''
											__a					       =						FlaxResNetModel(config=__lowercase		)
											__a					       =						model(__lowercase		)

											# Output shape (b, c, h, w)
											self.parent.assertEqual(
											    result.last_hidden_state.shape ,			(self.batch_size, self.hidden_sizes[-1], self.image_size // 32, self.image_size // 32) ,			)





							def   UpperCamelCase_   (				self						:						List[str] ,			__lowercase						:						Dict ,			__lowercase						:						Optional[int]		):

											'''simple docstring'''
											__a					       =						self.num_labels
											__a					       =						FlaxResNetForImageClassification(config=__lowercase		)
											__a					       =						model(__lowercase		)
											self.parent.assertEqual(result.logits.shape ,			(self.batch_size, self.num_labels)		)







							def   UpperCamelCase_   (				self						:						List[Any]		):

											'''simple docstring'''
											__a					       =						self.prepare_config_and_inputs()
											__a       ,   __a					       =						config_and_inputs
											__a					       =						{"""pixel_values""": pixel_values}
											return config, inputs_dict






@require_flax
class 				SCREAMING_SNAKE_CASE     (							lowerCamelCase__     , unittest.TestCase   ):
							__lowerCamelCase		:		int      =(FlaxResNetModel, FlaxResNetForImageClassification) if is_flax_available() else ()

							__lowerCamelCase		:		Union[str, Any]      =False
							__lowerCamelCase		:		Optional[Any]      =False
							__lowerCamelCase		:		str      =False





							def   UpperCamelCase_   (				self						:						Optional[Any]		):

											'''simple docstring'''
											__a					       =						FlaxResNetModelTester(self		)
											__a					       =						ConfigTester(self ,			config_class=__lowercase ,			has_text_modality=__lowercase		)





							def   UpperCamelCase_   (				self						:						str		):

											'''simple docstring'''
											self.create_and_test_config_common_properties()
											self.config_tester.create_and_test_config_to_json_string()
											self.config_tester.create_and_test_config_to_json_file()
											self.config_tester.create_and_test_config_from_and_save_pretrained()
											self.config_tester.create_and_test_config_with_num_labels()
											self.config_tester.check_config_can_be_init_without_params()
											self.config_tester.check_config_arguments_init()





							def   UpperCamelCase_   (				self						:						str		):

											'''simple docstring'''
											return





							def   UpperCamelCase_   (				self						:						Any		):

											'''simple docstring'''
											__a					       =						self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_model(*__lowercase		)





							def   UpperCamelCase_   (				self						:						Dict		):

											'''simple docstring'''
											__a					       =						self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_image_classification(*__lowercase		)





							@unittest.skip(reason="""ResNet does not use inputs_embeds"""		)
							def   UpperCamelCase_   (				self						:						Optional[Any]		):

											'''simple docstring'''
											pass





							@unittest.skip(reason="""ResNet does not support input and output embeddings"""		)
							def   UpperCamelCase_   (				self						:						int		):

											'''simple docstring'''
											pass





							def   UpperCamelCase_   (				self						:						int		):

											'''simple docstring'''
											__a       ,   __a					       =						self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
															__a					       =						model_class(__lowercase		)
															__a					       =						inspect.signature(model.__call__		)
															# signature.parameters is an OrderedDict => so arg_names order is deterministic
															__a					       =						[*signature.parameters.keys()]

															__a					       =						["""pixel_values"""]
															self.assertListEqual(arg_names[:1] ,			__lowercase		)





							def   UpperCamelCase_   (				self						:						Union[str, Any]		):

											'''simple docstring'''
											def check_hidden_states_output(__lowercase						:						Tuple ,			__lowercase						:						List[str] ,			__lowercase						:						str		):
															__a					       =						model_class(__lowercase		)

															__a					       =						model(**self._prepare_for_class(__lowercase ,			__lowercase		)		)

															__a					       =						outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

															__a					       =						self.model_tester.num_stages
															self.assertEqual(len(__lowercase		) ,			expected_num_stages + 1		)





							@unittest.skip(reason="""ResNet does not use feedforward chunking"""		)
							def   UpperCamelCase_   (				self						:						Optional[Any]		):

											'''simple docstring'''
											pass







							def   UpperCamelCase_   (				self						:						List[Any]		):

											'''simple docstring'''
											__a       ,   __a					       =						self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
															with self.subTest(model_class.__name__		):
																			__a					       =						self._prepare_for_class(__lowercase ,			__lowercase		)
																			__a					       =						model_class(__lowercase		)

																			@jax.jit
																			def model_jitted(__lowercase						:						List[str] ,			**__lowercase						:						Optional[int]		):
																							return model(pixel_values=__lowercase ,			**__lowercase		)

																			with self.subTest("""JIT Enabled"""		):
																							__a					       =						model_jitted(**__lowercase		).to_tuple()

																			with self.subTest("""JIT Disabled"""		):
																							with jax.disable_jit():
																											__a					       =						model_jitted(**__lowercase		).to_tuple()

																			self.assertEqual(len(__lowercase		) ,			len(__lowercase		)		)
																			for jitted_output, output in zip(__lowercase ,			__lowercase		):
																							self.assertEqual(jitted_output.shape ,			output.shape		)



def 					lowerCAmelCase__  (							):
				"""simple docstring"""







				__a					       =						Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""      )
				return image






@require_flax
class 				SCREAMING_SNAKE_CASE     (							unittest.TestCase   ):





							@cached_property
							def   UpperCamelCase_   (				self						:						Union[str, Any]		):

											'''simple docstring'''
											return AutoImageProcessor.from_pretrained("""microsoft/resnet-50"""		) if is_vision_available() else None







							@slow
							def   UpperCamelCase_   (				self						:						int		):

											'''simple docstring'''
											__a					       =						FlaxResNetForImageClassification.from_pretrained("""microsoft/resnet-50"""		)

											__a					       =						self.default_image_processor
											__a					       =						prepare_img()
											__a					       =						image_processor(images=__lowercase ,			return_tensors="""np"""		)

											__a					       =						model(**__lowercase		)

											# verify the logits
											__a					       =						(1, 1000)
											self.assertEqual(outputs.logits.shape ,			__lowercase		)

											__a					       =						jnp.array([-11.1069, -9.7877, -8.3777]		)

											self.assertTrue(jnp.allclose(outputs.logits[0, :3] ,			__lowercase ,			atol=1E-4		)		)
