


from collections import deque







def 			_SCREAMING_SNAKE_CASE    (       a  )				->				List[str]:
					return input(a  ).strip().split(' '  )







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				dict[int, list[int]]:
					__A     :						dict[int, list[int]]          =    {}
					for i in range(a  ):
										__A     :						List[str]          =    []

					for e in range(a  ):
										__A     :						List[str]          =    (int(a  ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """  ))
										graph[x].append(a  )
					return graph







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				dict[int, list[int]]:
					__A     :						dict[int, list[int]]          =    {}
					for i in range(a  ):
										__A     :						Any          =    []

					for e in range(a  ):
										__A     :						Union[str, Any]          =    (int(a  ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """  ))
										graph[x].append(a  )
										graph[y].append(a  )
					return graph







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				dict[int, list[tuple[int, int]]]:
					__A     :						dict[int, list[tuple[int, int]]]          =    {}
					for i in range(a  ):
										__A     :						Optional[int]          =    []

					for e in range(a  ):
										__A     :						Tuple          =    (int(a  ) 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__":
				UpperCAmelCase						:       Optional[Any]        =					(int(i) for i in _input('''Number of nodes and edges: '''))

				UpperCAmelCase						:       Optional[int]        =					int(
				    _input(
				        '''Press 1 or 2 or 3 \n'''
				        '''1. Unweighted directed \n'''
				        '''2. Unweighted undirected \n'''
				        '''3. Weighted undirected \n'''
				    )[0]
				)

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







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				int:
					__A     :						Any          =    {s}, [s]
					print(a  )
					while _s:
										__A     :						Optional[Any]          =    0
										for i in g[_s[-1]]:
															if i not in vis:
																				_s.append(a  )
																				vis.add(a  )
																				__A     :						Optional[int]          =    1
																				print(a  )
																				break
										if not flag:
															_s.pop()







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				Union[str, Any]:
					__A     :						Any          =    {s}, deque([s]  )
					print(a  )
					while q:
										__A     :						List[str]          =    q.popleft()
										for v in g[u]:
															if v not in vis:
																				vis.add(a  )
																				q.append(a  )
																				print(a  )







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				List[str]:
					__A     :						List[Any]          =    {s: 0}, set(), {s: 0}
					while True:
										if len(a  ) == len(a  ) - 1:
															break
										__A     :						Tuple          =    10_00_00
										for i in dist:
															if i not in known and dist[i] < mini:
																				__A     :						Union[str, Any]          =    dist[i]
																				__A     :						int          =    i
										known.add(a  )
										for v in g[u]:
															if v[0] not in known and dist[u] + v[1] < dist.get(v[0] ,						10_00_00  ):
																				__A     :						int          =    dist[u] + v[1]
																				__A     :						List[str]          =    u
					for i in dist:
										if i != s:
															print(dist[i]  )







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







def 			_SCREAMING_SNAKE_CASE    (       )				->				str:
					__A     :						int          =    input().strip()
					__A     :						List[str]          =    []
					for _ in range(a  ):
										a.append(map(a ,						input().strip().split()  )  )
					return a, n







def 			_SCREAMING_SNAKE_CASE    (       a  )				->				Dict:
					(__A)     :						int          =    a_and_n
					__A     :						Optional[int]          =    list(a  )
					__A     :						Union[str, Any]          =    [[0] * n for i in range(a  )]
					for k in range(a  ):
										for i in range(a  ):
															for j in range(a  ):
																				if dist[i][j] > dist[i][k] + dist[k][j]:
																									__A     :						str          =    dist[i][k] + dist[k][j]
																									__A     :						Dict          =    k
					print(a  )







def 			_SCREAMING_SNAKE_CASE    (       a ,						a  )				->				List[Any]:
					__A     :						Dict          =    {s: 0}, set(), {s: 0}
					while True:
										if len(a  ) == len(a  ) - 1:
															break
										__A     :						Dict          =    10_00_00
										for i in dist:
															if i not in known and dist[i] < mini:
																				__A     :						Dict          =    dist[i]
																				__A     :						Optional[Any]          =    i
										known.add(a  )
										for v in g[u]:
															if v[0] not in known and v[1] < dist.get(v[0] ,						10_00_00  ):
																				__A     :						Optional[Any]          =    v[1]
																				__A     :						Union[str, Any]          =    u
					return dist







def 			_SCREAMING_SNAKE_CASE    (       )				->				Tuple:
					__A     :						List[Any]          =    map(a ,						input().split(' '  )  )
					__A     :						List[Any]          =    []
					for _ in range(a  ):
										edges.append(map(a ,						input().split(' '  )  )  )
					return edges, n







def 			_SCREAMING_SNAKE_CASE    (       a  )				->				Dict:
					# Sort edges on the basis of distance
					(__A)     :						int          =    e_and_n
					e.sort(reverse=a ,						key=lambda a  : x[2]  )
					__A     :						Dict          =    [{i} for i in range(1 ,						n + 1  )]
					while True:
										if len(a  ) == 1:
															break
										print(a  )
										__A     :						Optional[int]          =    e.pop()
										for i in range(len(a  )  ):
															if x[0] in s[i]:
																				break
										for j in range(len(a  )  ):
															if x[1] in s[j]:
																				if i == j:
																									break
																				s[j].update(s[i]  )
																				s.pop(a  )
																				break







def 			_SCREAMING_SNAKE_CASE    (       a  )				->				List[Any]:
					__A     :						str          =    []
					for node in graph:
										if not graph[node]:
															isolated.append(a  )
					return isolated











import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin


if is_torch_available():
				import torch

if is_vision_available():
				from PIL import Image

				from transformers import TvltImageProcessor







def 			_SCREAMING_SNAKE_CASE    (       a ,						a=10 ,						a=10 ,						a=False ,						a=False  )				->				Union[str, Any]:
					__A     :						str          =    []
					for i in range(image_processor_tester.num_frames  ):
										video.append(np.random.randint(2_55 ,						size=(image_processor_tester.num_channels, width, height) ,						dtype=np.uinta  )  )

					if not numpify and not torchify:
										# PIL expects the channel dimension as last dimension
										__A     :						Union[str, Any]          =    [Image.fromarray(np.moveaxis(a ,						0 ,						-1  )  ) for frame in video]

					if torchify:
										__A     :						Dict          =    [torch.from_numpy(a  ) for frame in video]

					return video







def 			_SCREAMING_SNAKE_CASE    (       a ,						a=False ,						a=False ,						a=False  )				->				Union[str, Any]:
					assert not (numpify and torchify), "You cannot specify both numpy and PyTorch tensors at the same time"

					__A     :						List[Any]          =    []
					for i in range(image_processor_tester.batch_size  ):
										if equal_resolution:
															__A     :						int          =    image_processor_tester.max_resolution
										else:
															__A   ,    __A     :						Tuple          =    np.random.choice(
															    np.arange(image_processor_tester.min_resolution ,						image_processor_tester.max_resolution  ) ,						2  )
															__A     :						Optional[int]          =    prepare_video(
															    image_processor_tester=a ,						width=a ,						height=a ,						numpify=a ,						torchify=a ,						)
										video_inputs.append(a  )

					return video_inputs





class 						_A( unittest.TestCase       ):


				"""simple docstring"""


				def __init__(      self					, _A					, _A=7					, _A=3					, _A=4					, _A=18					, _A=30					, _A=400					, _A=True					, _A=None					, _A=True					, _A=[0.5, 0.5, 0.5]					, _A=[0.5, 0.5, 0.5]					, _A=True					, _A=None					, ):
									__A     :						List[str]          =    size if size is not None else {'shortest_edge': 18}
									__A     :						Tuple          =    crop_size if crop_size is not None else {'height': 18, 'width': 18}

									__A     :						Dict          =    parent
									__A     :						str          =    batch_size
									__A     :						int          =    num_channels
									__A     :						Optional[Any]          =    num_frames
									__A     :						Any          =    image_size
									__A     :						List[str]          =    min_resolution
									__A     :						List[Any]          =    max_resolution
									__A     :						Tuple          =    do_resize
									__A     :						List[str]          =    size
									__A     :						str          =    do_normalize
									__A     :						str          =    image_mean
									__A     :						int          =    image_std
									__A     :						Optional[Any]          =    do_center_crop
									__A     :						Union[str, Any]          =    crop_size





				def  UpperCAmelCase_		(      self					):
									return {
									    "image_mean": self.image_mean,
									    "image_std": self.image_std,
									    "do_normalize": self.do_normalize,
									    "do_resize": self.do_resize,
									    "size": self.size,
									    "do_center_crop": self.do_center_crop,
									    "crop_size": self.crop_size,
									}





@require_torch
@require_vision
class 						_A( snake_case__    ,			unittest.TestCase       ):


				"""simple docstring"""


				UpperCamelCase   :  Optional[Any]    =     TvltImageProcessor if is_vision_available() else None



				def  UpperCAmelCase_		(      self					):
									__A     :						str          =    TvltImageProcessorTester(self					)



				@property
				def  UpperCAmelCase_		(      self					):
									return self.image_processor_tester.prepare_image_processor_dict()



				def  UpperCAmelCase_		(      self					):
									__A     :						Union[str, Any]          =    self.image_processing_class(**self.image_processor_dict					)
									self.assertTrue(hasattr(_A					, 'image_mean'					)					)
									self.assertTrue(hasattr(_A					, 'image_std'					)					)
									self.assertTrue(hasattr(_A					, 'do_normalize'					)					)
									self.assertTrue(hasattr(_A					, 'do_resize'					)					)
									self.assertTrue(hasattr(_A					, 'do_center_crop'					)					)
									self.assertTrue(hasattr(_A					, 'size'					)					)



				def  UpperCAmelCase_		(      self					):
									# Initialize image_processor
									__A     :						List[str]          =    self.image_processing_class(**self.image_processor_dict					)
									# create random PIL videos
									__A     :						List[str]          =    prepare_video_inputs(self.image_processor_tester					, equal_resolution=_A					)
									for video in video_inputs:
														self.assertIsInstance(_A					, _A					)
														self.assertIsInstance(video[0]					, Image.Image					)

									# Test not batched input
									__A     :						str          =    image_processor(video_inputs[0]					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        1,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )

									# Test batched
									__A     :						List[Any]          =    image_processor(_A					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        self.image_processor_tester.batch_size,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )



				def  UpperCAmelCase_		(      self					):
									# Initialize image_processor
									__A     :						Any          =    self.image_processing_class(**self.image_processor_dict					)
									# create random numpy tensors
									__A     :						Dict          =    prepare_video_inputs(self.image_processor_tester					, equal_resolution=_A					, numpify=_A					)
									for video in video_inputs:
														self.assertIsInstance(_A					, _A					)
														self.assertIsInstance(video[0]					, np.ndarray					)

									# Test not batched input
									__A     :						Dict          =    image_processor(video_inputs[0]					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        1,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )

									# Test batched
									__A     :						Optional[int]          =    image_processor(_A					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        self.image_processor_tester.batch_size,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )





				def  UpperCAmelCase_		(      self					):
									# Initialize image_processor
									__A     :						Any          =    self.image_processing_class(**self.image_processor_dict					)
									# create random PyTorch tensors
									__A     :						Dict          =    prepare_video_inputs(self.image_processor_tester					, equal_resolution=_A					, torchify=_A					)
									for video in video_inputs:
														self.assertIsInstance(_A					, _A					)
														self.assertIsInstance(video[0]					, torch.Tensor					)

									# Test not batched input
									__A     :						Optional[Any]          =    image_processor(video_inputs[0]					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        1,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )

									# Test batched
									__A     :						int          =    image_processor(_A					, return_tensors='pt'					).pixel_values
									self.assertEqual(
									    encoded_videos.shape					, (
									        self.image_processor_tester.batch_size,
									        self.image_processor_tester.num_frames,
									        self.image_processor_tester.num_channels,
									        self.image_processor_tester.crop_size['height'],
									        self.image_processor_tester.crop_size['width'],
									    )					, )




