


from collections import deque



def      __lowerCAmelCase    (				snake_case						:     Union[str, Any]			)							->				Tuple:
   return input(snake_case			).strip().split(""" """			)



def      __lowerCAmelCase    (				snake_case						:     int    ,   snake_case						:     int			)							->				dict[int, list[int]]:
   __lowerCamelCase:					dict[int, list[int]]	 =						{}
   for i in range(snake_case			):
      __lowerCamelCase:					List[str]	 =						[]

   for e in range(snake_case			):
      __lowerCamelCase ,  __lowerCamelCase:					List[str]	 =						(int(snake_case			) for i in _input(f'Edge {e + 1}: <node1> <node2> '			))
      graph[x].append(snake_case			)
   return graph



def      __lowerCAmelCase    (				snake_case						:     int    ,   snake_case						:     int			)							->				dict[int, list[int]]:
   __lowerCamelCase:					dict[int, list[int]]	 =						{}
   for i in range(snake_case			):
      __lowerCamelCase:					List[str]	 =						[]

   for e in range(snake_case			):
      __lowerCamelCase ,  __lowerCamelCase:					Any	 =						(int(snake_case			) for i in _input(f'Edge {e + 1}: <node1> <node2> '			))
      graph[x].append(snake_case			)
      graph[y].append(snake_case			)
   return graph



def      __lowerCAmelCase    (				snake_case						:     int    ,   snake_case						:     int			)							->				dict[int, list[tuple[int, int]]]:
   __lowerCamelCase:					dict[int, list[tuple[int, int]]]	 =						{}
   for i in range(snake_case			):
      __lowerCamelCase:					Dict	 =						[]

   for e in range(snake_case			):
      __lowerCamelCase ,  __lowerCamelCase ,  __lowerCamelCase:					Optional[Any]	 =						(int(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__":
   _A    ,_A		:					Dict          =							(int(i) for i in _input('''Number of nodes and edges: '''))

   _A		:					Union[str, Any]          =							int(
       _input(
           '''Press 1 or 2 or 3 \n'''
           '''1. Unweighted directed \n'''
           '''2. Unweighted undirected \n'''
           '''3. Weighted undirected \n'''
       )[0]
   )

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



def      __lowerCAmelCase    (				snake_case						:     Union[str, Any]    ,   snake_case						:     Any			)							->				Optional[int]:
   __lowerCamelCase ,  __lowerCamelCase:					Dict	 =						{s}, [s]
   print(snake_case			)
   while _s:
      __lowerCamelCase:					Optional[Any]	 =						0
      for i in g[_s[-1]]:
         if i not in vis:
            _s.append(snake_case			)
            vis.add(snake_case			)
            __lowerCamelCase:					Optional[int]	 =						1
            print(snake_case			)
            break
      if not flag:
         _s.pop()



def      __lowerCAmelCase    (				snake_case						:     List[str]    ,   snake_case						:     Optional[int]			)							->				int:
   __lowerCamelCase ,  __lowerCamelCase:					Optional[Any]	 =						{s}, deque([s]			)
   print(snake_case			)
   while q:
      __lowerCamelCase:					str	 =						q.popleft()
      for v in g[u]:
         if v not in vis:
            vis.add(snake_case			)
            q.append(snake_case			)
            print(snake_case			)



def      __lowerCAmelCase    (				snake_case						:     List[str]    ,   snake_case						:     List[Any]			)							->				List[Any]:
   __lowerCamelCase ,  __lowerCamelCase ,  __lowerCamelCase:					List[str]	 =						{s: 0}, set(), {s: 0}
   while True:
      if len(snake_case			) == len(snake_case			) - 1:
         break
      __lowerCamelCase:					List[Any]	 =						100000
      for i in dist:
         if i not in known and dist[i] < mini:
            __lowerCamelCase:					Optional[Any]	 =						dist[i]
            __lowerCamelCase:					List[Any]	 =						i
      known.add(snake_case			)
      for v in g[u]:
         if v[0] not in known and dist[u] + v[1] < dist.get(v[0]    ,   100000			):
            __lowerCamelCase:					Union[str, Any]	 =						dist[u] + v[1]
            __lowerCamelCase:					str	 =						u
   for i in dist:
      if i != s:
         print(dist[i]			)



def      __lowerCAmelCase    (				snake_case						:     Tuple    ,   snake_case						:     Optional[int]=None    ,   snake_case						:     int=None			)							->				Optional[int]:
   if q is None:
      __lowerCamelCase:					Dict	 =						[1]
   if ind is None:
      __lowerCamelCase:					Union[str, Any]	 =						[0] * (len(snake_case			) + 1)  # SInce oth Index is ignored
      for u in g:
         for v in g[u]:
            ind[v] += 1
      __lowerCamelCase:					str	 =						deque()
      for i in g:
         if ind[i] == 0:
            q.append(snake_case			)
   if len(snake_case			) == 0:
      return
   __lowerCamelCase:					Union[str, Any]	 =						q.popleft()
   print(snake_case			)
   for w in g[v]:
      ind[w] -= 1
      if ind[w] == 0:
         q.append(snake_case			)
   topo(snake_case    ,   snake_case    ,   snake_case			)



def      __lowerCAmelCase    (				)							->				Optional[Any]:
   __lowerCamelCase:					Union[str, Any]	 =						input().strip()
   __lowerCamelCase:					str	 =						[]
   for _ in range(snake_case			):
      a.append(map(snake_case    ,   input().strip().split()			)			)
   return a, n



def      __lowerCAmelCase    (				snake_case						:     Union[str, Any]			)							->				Union[str, Any]:
   ((__lowerCamelCase) ,  (__lowerCamelCase)):					List[Any]	 =						a_and_n
   __lowerCamelCase:					Tuple	 =						list(snake_case			)
   __lowerCamelCase:					Any	 =						[[0] * n for i in range(snake_case			)]
   for k in range(snake_case			):
      for i in range(snake_case			):
         for j in range(snake_case			):
            if dist[i][j] > dist[i][k] + dist[k][j]:
               __lowerCamelCase:					List[str]	 =						dist[i][k] + dist[k][j]
               __lowerCamelCase:					Any	 =						k
   print(snake_case			)



def      __lowerCAmelCase    (				snake_case						:     Optional[Any]    ,   snake_case						:     Optional[Any]			)							->				Any:
   __lowerCamelCase ,  __lowerCamelCase ,  __lowerCamelCase:					List[Any]	 =						{s: 0}, set(), {s: 0}
   while True:
      if len(snake_case			) == len(snake_case			) - 1:
         break
      __lowerCamelCase:					Any	 =						100000
      for i in dist:
         if i not in known and dist[i] < mini:
            __lowerCamelCase:					int	 =						dist[i]
            __lowerCamelCase:					Tuple	 =						i
      known.add(snake_case			)
      for v in g[u]:
         if v[0] not in known and v[1] < dist.get(v[0]    ,   100000			):
            __lowerCamelCase:					Optional[int]	 =						v[1]
            __lowerCamelCase:					str	 =						u
   return dist



def      __lowerCAmelCase    (				)							->				Union[str, Any]:
   __lowerCamelCase ,  __lowerCamelCase:					Optional[int]	 =						map(snake_case    ,   input().split(""" """			)			)
   __lowerCamelCase:					List[str]	 =						[]
   for _ in range(snake_case			):
      edges.append(map(snake_case    ,   input().split(""" """			)			)			)
   return edges, n



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







def      __lowerCAmelCase    (				snake_case						:     Optional[Any]			)							->				Dict:
   __lowerCamelCase:					Dict	 =						[]
   for node in graph:
      if not graph[node]:
         isolated.append(snake_case			)
   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, prepare_image_inputs


if is_torch_available():
   import torch

if is_vision_available():
   from PIL import Image

   from transformers import MobileNetVaImageProcessor



class 							a       (      unittest.TestCase ):





     def __init__(     self       :					Optional[int]     ,						SCREAMING_SNAKE_CASE_       :					str     ,						SCREAMING_SNAKE_CASE_       :					List[str]=7     ,						SCREAMING_SNAKE_CASE_       :					Union[str, Any]=3     ,						SCREAMING_SNAKE_CASE_       :					List[Any]=18     ,						SCREAMING_SNAKE_CASE_       :					List[str]=30     ,						SCREAMING_SNAKE_CASE_       :					List[Any]=400     ,						SCREAMING_SNAKE_CASE_       :					Dict=True     ,						SCREAMING_SNAKE_CASE_       :					Any=None     ,						SCREAMING_SNAKE_CASE_       :					List[str]=True     ,						SCREAMING_SNAKE_CASE_       :					Any=None     ,						):
        __lowerCamelCase:					List[Any]	 =						size if size is not None else {"""shortest_edge""": 20}
        __lowerCamelCase:					Tuple	 =						crop_size if crop_size is not None else {"""height""": 18, """width""": 18}
        __lowerCamelCase:					List[Any]	 =						parent
        __lowerCamelCase:					Optional[int]	 =						batch_size
        __lowerCamelCase:					str	 =						num_channels
        __lowerCamelCase:					Dict	 =						image_size
        __lowerCamelCase:					Tuple	 =						min_resolution
        __lowerCamelCase:					Union[str, Any]	 =						max_resolution
        __lowerCamelCase:					Tuple	 =						do_resize
        __lowerCamelCase:					List[str]	 =						size
        __lowerCamelCase:					int	 =						do_center_crop
        __lowerCamelCase:					Tuple	 =						crop_size







     def 			SCREAMING_SNAKE_CASE__							(     self       :					List[Any]				):
        return {
            "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       (      _UpperCAmelCase  ,unittest.TestCase ):
     UpperCAmelCase__			:	int       =						MobileNetVaImageProcessor if is_vision_available() else None





     def 			SCREAMING_SNAKE_CASE__							(     self       :					List[str]				):
        __lowerCamelCase:					Tuple	 =						MobileNetVaImageProcessingTester(self				)





     @property
     def 			SCREAMING_SNAKE_CASE__							(     self       :					str				):
        return self.image_processor_tester.prepare_image_processor_dict()





     def 			SCREAMING_SNAKE_CASE__							(     self       :					List[str]				):
        __lowerCamelCase:					List[Any]	 =						self.image_processing_class(**self.image_processor_dict				)
        self.assertTrue(hasattr(SCREAMING_SNAKE_CASE_     ,						"""do_resize"""				)				)
        self.assertTrue(hasattr(SCREAMING_SNAKE_CASE_     ,						"""size"""				)				)
        self.assertTrue(hasattr(SCREAMING_SNAKE_CASE_     ,						"""do_center_crop"""				)				)
        self.assertTrue(hasattr(SCREAMING_SNAKE_CASE_     ,						"""center_crop"""				)				)





     def 			SCREAMING_SNAKE_CASE__							(     self       :					Any				):
        __lowerCamelCase:					str	 =						self.image_processing_class.from_dict(self.image_processor_dict				)
        self.assertEqual(image_processor.size     ,						{"""shortest_edge""": 20}				)
        self.assertEqual(image_processor.crop_size     ,						{"""height""": 18, """width""": 18}				)

        __lowerCamelCase:					Optional[int]	 =						self.image_processing_class.from_dict(self.image_processor_dict     ,						size=42     ,						crop_size=84				)
        self.assertEqual(image_processor.size     ,						{"""shortest_edge""": 42}				)
        self.assertEqual(image_processor.crop_size     ,						{"""height""": 84, """width""": 84}				)





     def 			SCREAMING_SNAKE_CASE__							(     self       :					Optional[Any]				):
        pass





     def 			SCREAMING_SNAKE_CASE__							(     self       :					Optional[int]				):
        # Initialize image_processing
        __lowerCamelCase:					List[str]	 =						self.image_processing_class(**self.image_processor_dict				)
        # create random PIL images
        __lowerCamelCase:					str	 =						prepare_image_inputs(self.image_processor_tester     ,						equal_resolution=SCREAMING_SNAKE_CASE_				)
        for image in image_inputs:
           self.assertIsInstance(SCREAMING_SNAKE_CASE_     ,						Image.Image				)

        # Test not batched input
        __lowerCamelCase:					Optional[Any]	 =						image_processing(image_inputs[0]     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)

        # Test batched
        __lowerCamelCase:					Tuple	 =						image_processing(SCREAMING_SNAKE_CASE_     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)





     def 			SCREAMING_SNAKE_CASE__							(     self       :					Optional[int]				):
        # Initialize image_processing
        __lowerCamelCase:					Union[str, Any]	 =						self.image_processing_class(**self.image_processor_dict				)
        # create random numpy tensors
        __lowerCamelCase:					Tuple	 =						prepare_image_inputs(self.image_processor_tester     ,						equal_resolution=SCREAMING_SNAKE_CASE_     ,						numpify=SCREAMING_SNAKE_CASE_				)
        for image in image_inputs:
           self.assertIsInstance(SCREAMING_SNAKE_CASE_     ,						np.ndarray				)

        # Test not batched input
        __lowerCamelCase:					List[Any]	 =						image_processing(image_inputs[0]     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)

        # Test batched
        __lowerCamelCase:					Optional[Any]	 =						image_processing(SCREAMING_SNAKE_CASE_     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)







     def 			SCREAMING_SNAKE_CASE__							(     self       :					Optional[int]				):
        # Initialize image_processing
        __lowerCamelCase:					str	 =						self.image_processing_class(**self.image_processor_dict				)
        # create random PyTorch tensors
        __lowerCamelCase:					List[str]	 =						prepare_image_inputs(self.image_processor_tester     ,						equal_resolution=SCREAMING_SNAKE_CASE_     ,						torchify=SCREAMING_SNAKE_CASE_				)
        for image in image_inputs:
           self.assertIsInstance(SCREAMING_SNAKE_CASE_     ,						torch.Tensor				)

        # Test not batched input
        __lowerCamelCase:					Union[str, Any]	 =						image_processing(image_inputs[0]     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)

        # Test batched
        __lowerCamelCase:					Optional[int]	 =						image_processing(SCREAMING_SNAKE_CASE_     ,						return_tensors="""pt"""				).pixel_values
        self.assertEqual(
            encoded_images.shape     ,						(
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.crop_size["""height"""],
                self.image_processor_tester.crop_size["""width"""],
            )     ,						)


