


from collections import deque






def 						_A						(						_lowercase				)			->				List[str]:


     """simple docstring"""


     return input(_lowercase				).strip().split(' '				)






def 						_A						(						_lowercase			,       _lowercase				)			->				dict[int, list[int]]:


     """simple docstring"""


     __UpperCamelCase				=	{}
     for i in range(_lowercase				):
          __UpperCamelCase				=	[]

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






def 						_A						(						_lowercase			,       _lowercase				)			->				dict[int, list[int]]:


     """simple docstring"""


     __UpperCamelCase				=	{}
     for i in range(_lowercase				):
          __UpperCamelCase				=	[]

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






def 						_A						(						_lowercase			,       _lowercase				)			->				dict[int, list[tuple[int, int]]]:


     """simple docstring"""


     __UpperCamelCase				=	{}
     for i in range(_lowercase				):
          __UpperCamelCase				=	[]

     for e in range(_lowercase				):
          __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase				=	(int(_lowercase				) 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__":
    __snake_case    ,					__snake_case     =		(int(i) for i in _input('''Number of nodes and edges: '''))

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

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






def 						_A						(						_lowercase			,       _lowercase				)			->				List[str]:


     """simple docstring"""


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






def 						_A						(						_lowercase			,       _lowercase				)			->				List[Any]:


     """simple docstring"""


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






def 						_A						(						_lowercase			,       _lowercase				)			->				List[str]:


     """simple docstring"""


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






def 						_A						(						_lowercase			,       _lowercase=None			,       _lowercase=None				)			->				Tuple:


     """simple docstring"""


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






def 						_A						(						)			->				int:


     """simple docstring"""


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






def 						_A						(						_lowercase				)			->				List[Any]:


     """simple docstring"""


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






def 						_A						(						_lowercase			,       _lowercase				)			->				Tuple:


     """simple docstring"""


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






def 						_A						(						)			->				Any:


     """simple docstring"""


     __UpperCamelCase,  __UpperCamelCase				=	map(_lowercase			,       input().split(' '				)				)
     __UpperCamelCase				=	[]
     for _ in range(_lowercase				):
          edges.append(map(_lowercase			,       input().split(' '				)				)				)
     return edges, n






def 						_A						(						_lowercase				)			->				int:


     """simple docstring"""


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






def 						_A						(						_lowercase				)			->				Tuple:


     """simple docstring"""


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






import inspect
import json
import os
import tempfile
import unittest

from transformers.models.speech_to_text_a import SpeechaTextaTokenizer
from transformers.models.speech_to_text_a.tokenization_speech_to_text_a import VOCAB_FILES_NAMES

from ...test_tokenization_common import TokenizerTesterMixin



class 					__lowerCamelCase	(_a							,     unittest.TestCase		):
       _lowercase    							=      SpeechaTextaTokenizer
       _lowercase    							=      False







       def 						snake_case_					(	self:				str			):






            '''simple docstring'''




            super().setUp()

            __UpperCamelCase				=	'<s> <pad> </s> <unk> here@@ a couple of@@ words for the he@@ re@@ vocab'.split(' '			)
            __UpperCamelCase				=	['he re</w> 123', 'here a 1456']
            __UpperCamelCase				=	dict(zip(A_,range(len(A_			)			)			)			)

            __UpperCamelCase				=	{'pad_token': '<pad>', 'unk_token': '<unk>', 'bos_token': '<s>', 'eos_token': '</s>'}

            __UpperCamelCase				=	tempfile.mkdtemp()
            __UpperCamelCase				=	os.path.join(self.tmpdirname,VOCAB_FILES_NAMES['vocab_file']			)
            __UpperCamelCase				=	os.path.join(self.tmpdirname,VOCAB_FILES_NAMES['merges_file']			)

            with open(self.vocab_file,'w',encoding='utf-8'			) as fp:
                 fp.write(json.dumps(A_			) + '\n'			)

            with open(self.merges_file,'w'			) as fp:
                 fp.write('\n'.join(A_			)			)







       def 						snake_case_					(	self:				Optional[int]			):






            '''simple docstring'''




            __UpperCamelCase				=	list(self.get_tokenizer().get_vocab().keys()			)

            self.assertEqual(vocab_keys[0],'<s>'			)
            self.assertEqual(vocab_keys[1],'<pad>'			)
            self.assertEqual(vocab_keys[-1],'vocab'			)
            self.assertEqual(len(A_			),14			)







       def 						snake_case_					(	self:				str			):






            '''simple docstring'''




            self.assertEqual(self.get_tokenizer().vocab_size,14			)







       def 						snake_case_					(	self:				Dict			):






            '''simple docstring'''




            __UpperCamelCase				=	SpeechaTextaTokenizer.from_pretrained(self.tmpdirname			)

            # make sure @@ is correctly concatenated
            __UpperCamelCase				=	[4, 6, 8, 7, 10]  # ["here@@", "couple", "words", "of@@", "the"]
            __UpperCamelCase				=	tokenizer.decode(A_			)

            self.assertTrue(output_string == 'herecouple words ofthe'			)







       def 						snake_case_					(	self:				int			):






            '''simple docstring'''




            __UpperCamelCase				=	SpeechaTextaTokenizer.from_pretrained(self.tmpdirname			)

            with tempfile.TemporaryDirectory() as tmp_dirname:
                 tokenizer.save_pretrained(A_			)
                 os.remove(os.path.join(A_,'merges.txt'			)			)

                 # load tokenizer without merges file should not throw an error
                 __UpperCamelCase				=	SpeechaTextaTokenizer.from_pretrained(A_			)

            with tempfile.TemporaryDirectory() as tmp_dirname:
                 # save tokenizer and load again
                 tokenizer.save_pretrained(A_			)
                 __UpperCamelCase				=	SpeechaTextaTokenizer.from_pretrained(A_			)

            self.assertIsNotNone(A_			)







       def 						snake_case_					(	self:				str			):






            '''simple docstring'''




            if not self.test_slow_tokenizer:
                 return

            __UpperCamelCase				=	inspect.signature(self.tokenizer_class.__init__			)
            __UpperCamelCase				=	self.get_tokenizer()

            for parameter_name, parameter in signature.parameters.items():
                 if parameter.default != inspect.Parameter.empty and parameter_name != "merges_file":
                      self.assertIn(A_,tokenizer.init_kwargs			)


