"""simple docstring"""

from collections import deque


def    lowerCAmelCase			(__UpperCamelCase							:    Optional[Any]			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    int							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


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

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


def    lowerCAmelCase			(__UpperCamelCase							:    int							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


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

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


def    lowerCAmelCase			(__UpperCamelCase							:    int							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


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

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

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

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


def    lowerCAmelCase			(__UpperCamelCase							:    Tuple							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    List[str]							,					__UpperCamelCase							:    Optional[int]			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    int							,					__UpperCamelCase							:    Dict			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    str							,					__UpperCamelCase							:    Dict=None							,					__UpperCamelCase							:    str=None			):
							"""simple docstring"""


							if q is None:
														__UpperCamelCase							=[1]
							if ind is None:
														__UpperCamelCase							=[0] * (len(__UpperCamelCase			) + 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(__UpperCamelCase			)
							if len(__UpperCamelCase			) == 0:
														return
							__UpperCamelCase							=q.popleft()
							print(__UpperCamelCase			)
							for w in g[v]:
														ind[w] -= 1
														if ind[w] == 0:
																					q.append(__UpperCamelCase			)
							topo(__UpperCamelCase							,					__UpperCamelCase							,					__UpperCamelCase			)


def    lowerCAmelCase			():
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    Any			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    Optional[Any]							,					__UpperCamelCase							:    str			):
							"""simple docstring"""


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


def    lowerCAmelCase			():
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    Optional[int]			):
							"""simple docstring"""


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






def    lowerCAmelCase			(__UpperCamelCase							:    Any			):
							"""simple docstring"""


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




"""simple docstring"""

from copy import deepcopy
from unittest.case import TestCase

import pytest

from datasets.arrow_dataset import Dataset
from datasets.features import Audio, ClassLabel, Features, Image, Sequence, Value
from datasets.info import DatasetInfo
from datasets.tasks import (
    AudioClassification,
    AutomaticSpeechRecognition,
    ImageClassification,
    LanguageModeling,
    QuestionAnsweringExtractive,
    Summarization,
    TextClassification,
    task_template_from_dict,
)
from datasets.utils.py_utils import asdict


__lowercase    =				{
    '''id''': '''5733be284776f41900661182''',
    '''title''': '''University_of_Notre_Dame''',
    '''context''': '''Architecturally, the school has a Catholic character. Atop the Main Building\'s gold dome is a golden statue of the Virgin Mary. Immediately in front of the Main Building and facing it, is a copper statue of Christ with arms upraised with the legend "Venite Ad Me Omnes". Next to the Main Building is the Basilica of the Sacred Heart. Immediately behind the basilica is the Grotto, a Marian place of prayer and reflection. It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858. At the end of the main drive (and in a direct line that connects through 3 statues and the Gold Dome), is a simple, modern stone statue of Mary.''',
    '''question''': '''To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?''',
    '''answers''': {'''text''': ['''Saint Bernadette Soubirous'''], '''answer_start''': [515]},
}


@pytest.mark.parametrize(
    '''task_cls'''							,					[
        AudioClassification,
        AutomaticSpeechRecognition,
        ImageClassification,
        LanguageModeling,
        QuestionAnsweringExtractive,
        Summarization,
        TextClassification,
    ]							,					)
def    lowerCAmelCase			(__UpperCamelCase							:    List[str]			):
							"""simple docstring"""


							__UpperCamelCase							=task_cls()
							__UpperCamelCase							=asdict(__UpperCamelCase			)
							__UpperCamelCase							=task_template_from_dict(__UpperCamelCase			)
							assert task == reloaded






class 		_lowercase :



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    Union[str, Any]				)				->				List[Any]:
													'''simple docstring'''



													__UpperCamelCase							=LanguageModeling(text_column='''input_text'''				)
													assert {"input_text": "text"} == task.column_mapping





						def   UpperCAmelCase_ (				self							:    str				)				->				int:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''text''': Value('''string'''				)}				)
													__UpperCamelCase							={'''text_column''': '''input_text'''}
													__UpperCamelCase							=LanguageModeling.from_dict(UpperCamelCase__				)
													assert "language-modeling" == task.task
													assert input_schema == task.input_schema






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    Optional[Any]				)				->				Dict:
													'''simple docstring'''



													__UpperCamelCase							=sorted(['''pos''', '''neg''']				)





						def   UpperCAmelCase_ (				self							:    Tuple				)				->				Tuple:
													'''simple docstring'''



													__UpperCamelCase							=TextClassification(text_column='''input_text'''     , label_column='''input_label'''				)
													self.assertDictEqual({'''input_text''': '''text''', '''input_label''': '''labels'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    Union[str, Any]				)				->				Union[str, Any]:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''text''': Value('''string'''				)}				)
													# Labels are cast to tuple during `TextClassification.__post_init__`, so we do the same here
													__UpperCamelCase							=Features({'''labels''': ClassLabel}				)
													__UpperCamelCase							={'''text_column''': '''input_text''', '''label_column''': '''input_labels'''}
													__UpperCamelCase							=TextClassification.from_dict(UpperCamelCase__				)
													self.assertEqual('''text-classification'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)





						def   UpperCAmelCase_ (				self							:    Tuple				)				->				Optional[Any]:
													'''simple docstring'''



													__UpperCamelCase							=TextClassification(text_column='''input_text'''     , label_column='''input_label'''				)
													self.assertEqual(task.label_schema['''labels''']     , UpperCamelCase__				)
													__UpperCamelCase							=task.align_with_features(Features({'''input_label''': ClassLabel(names=self.labels				)}				)				)
													self.assertEqual(task.label_schema['''labels''']     , ClassLabel(names=self.labels				)				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    Dict				)				->				List[Any]:
													'''simple docstring'''



													__UpperCamelCase							=QuestionAnsweringExtractive(
													    context_column='''input_context'''     , question_column='''input_question'''     , answers_column='''input_answers'''				)
													self.assertDictEqual(
													    {'''input_context''': '''context''', '''input_question''': '''question''', '''input_answers''': '''answers'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    Optional[Any]				)				->				Optional[Any]:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''question''': Value('''string'''				), '''context''': Value('''string'''				)}				)
													__UpperCamelCase							=Features(
													    {
													        '''answers''': Sequence(
													            {
													                '''text''': Value('''string'''				),
													                '''answer_start''': Value('''int32'''				),
													            }				)
													    }				)
													__UpperCamelCase							={
													    '''context_column''': '''input_input_context''',
													    '''question_column''': '''input_question''',
													    '''answers_column''': '''input_answers''',
													}
													__UpperCamelCase							=QuestionAnsweringExtractive.from_dict(UpperCamelCase__				)
													self.assertEqual('''question-answering-extractive'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    List[Any]				)				->				str:
													'''simple docstring'''



													__UpperCamelCase							=Summarization(text_column='''input_text'''     , summary_column='''input_summary'''				)
													self.assertDictEqual({'''input_text''': '''text''', '''input_summary''': '''summary'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    int				)				->				List[Any]:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''text''': Value('''string'''				)}				)
													__UpperCamelCase							=Features({'''summary''': Value('''string'''				)}				)
													__UpperCamelCase							={'''text_column''': '''input_text''', '''summary_column''': '''input_summary'''}
													__UpperCamelCase							=Summarization.from_dict(UpperCamelCase__				)
													self.assertEqual('''summarization'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    List[Any]				)				->				Dict:
													'''simple docstring'''



													__UpperCamelCase							=AutomaticSpeechRecognition(audio_column='''input_audio'''     , transcription_column='''input_transcription'''				)
													self.assertDictEqual({'''input_audio''': '''audio''', '''input_transcription''': '''transcription'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    Union[str, Any]				)				->				List[str]:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''audio''': Audio()}				)
													__UpperCamelCase							=Features({'''transcription''': Value('''string'''				)}				)
													__UpperCamelCase							={
													    '''audio_column''': '''input_audio''',
													    '''transcription_column''': '''input_transcription''',
													}
													__UpperCamelCase							=AutomaticSpeechRecognition.from_dict(UpperCamelCase__				)
													self.assertEqual('''automatic-speech-recognition'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    List[str]				)				->				List[str]:
													'''simple docstring'''



													__UpperCamelCase							=sorted(['''pos''', '''neg''']				)





						def   UpperCAmelCase_ (				self							:    Union[str, Any]				)				->				int:
													'''simple docstring'''



													__UpperCamelCase							=AudioClassification(audio_column='''input_audio'''     , label_column='''input_label'''				)
													self.assertDictEqual({'''input_audio''': '''audio''', '''input_label''': '''labels'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    Dict				)				->				Any:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''audio''': Audio()}				)
													__UpperCamelCase							=Features({'''labels''': ClassLabel}				)
													__UpperCamelCase							={
													    '''audio_column''': '''input_image''',
													    '''label_column''': '''input_label''',
													}
													__UpperCamelCase							=AudioClassification.from_dict(UpperCamelCase__				)
													self.assertEqual('''audio-classification'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)





						def   UpperCAmelCase_ (				self							:    Tuple				)				->				List[str]:
													'''simple docstring'''



													__UpperCamelCase							=AudioClassification(audio_column='''input_audio'''     , label_column='''input_label'''				)
													self.assertEqual(task.label_schema['''labels''']     , UpperCamelCase__				)
													__UpperCamelCase							=task.align_with_features(Features({'''input_label''': ClassLabel(names=self.labels				)}				)				)
													self.assertEqual(task.label_schema['''labels''']     , ClassLabel(names=self.labels				)				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    Optional[Any]				)				->				str:
													'''simple docstring'''



													__UpperCamelCase							=sorted(['''pos''', '''neg''']				)





						def   UpperCAmelCase_ (				self							:    str				)				->				Tuple:
													'''simple docstring'''



													__UpperCamelCase							=ImageClassification(image_column='''input_image'''     , label_column='''input_label'''				)
													self.assertDictEqual({'''input_image''': '''image''', '''input_label''': '''labels'''}     , task.column_mapping				)





						def   UpperCAmelCase_ (				self							:    Optional[Any]				)				->				List[str]:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''image''': Image()}				)
													__UpperCamelCase							=Features({'''labels''': ClassLabel}				)
													__UpperCamelCase							={
													    '''image_column''': '''input_image''',
													    '''label_column''': '''input_label''',
													}
													__UpperCamelCase							=ImageClassification.from_dict(UpperCamelCase__				)
													self.assertEqual('''image-classification'''     , task.task				)
													self.assertEqual(UpperCamelCase__     , task.input_schema				)
													self.assertEqual(UpperCamelCase__     , task.label_schema				)





						def   UpperCAmelCase_ (				self							:    str				)				->				Optional[int]:
													'''simple docstring'''



													__UpperCamelCase							=ImageClassification(image_column='''input_image'''     , label_column='''input_label'''				)
													self.assertEqual(task.label_schema['''labels''']     , UpperCamelCase__				)
													__UpperCamelCase							=task.align_with_features(Features({'''input_label''': ClassLabel(names=self.labels				)}				)				)
													self.assertEqual(task.label_schema['''labels''']     , ClassLabel(names=self.labels				)				)






class 		_lowercase (						__a      ):



						"""simple docstring"""




						def   UpperCAmelCase_ (				self							:    Optional[Any]				)				->				List[Any]:
													'''simple docstring'''



													__UpperCamelCase							=DatasetInfo(task_templates=QuestionAnsweringExtractive()				)
													__UpperCamelCase							=Dataset.from_dict({k: [v] for k, v in SAMPLE_QUESTION_ANSWERING_EXTRACTIVE.items()}     , info=UpperCamelCase__				)
													assert isinstance(dataset.info.task_templates     , UpperCamelCase__				)
													assert len(dataset.info.task_templates				) == 1

													def keep_task(UpperCamelCase__							:    Optional[int]				):
																				return x

													def dont_keep_task(UpperCamelCase__							:    Optional[int]				):
																				__UpperCamelCase							=deepcopy(UpperCamelCase__				)
																				__UpperCamelCase							=0
																				return out

													__UpperCamelCase							=dataset.map(UpperCamelCase__				)
													assert mapped_dataset.info.task_templates == dataset.info.task_templates
													# reload from cache
													__UpperCamelCase							=dataset.map(UpperCamelCase__				)
													assert mapped_dataset.info.task_templates == dataset.info.task_templates

													__UpperCamelCase							=dataset.map(UpperCamelCase__				)
													assert mapped_dataset.info.task_templates == []
													# reload from cache
													__UpperCamelCase							=dataset.map(UpperCamelCase__				)
													assert mapped_dataset.info.task_templates == []





						def   UpperCAmelCase_ (				self							:    List[str]				)				->				Dict:
													'''simple docstring'''



													__UpperCamelCase							=Features({'''text''': Value('''string'''				), '''label''': ClassLabel(names=('''pos''', '''neg''')				)}				)
													__UpperCamelCase							=TextClassification(text_column='''text'''     , label_column='''label'''				)
													__UpperCamelCase							=DatasetInfo(features=UpperCamelCase__     , task_templates=UpperCamelCase__				)
													__UpperCamelCase							=Dataset.from_dict({'''text''': ['''A sentence.'''], '''label''': ['''pos''']}     , info=UpperCamelCase__				)

													def process(UpperCamelCase__							:    Any				):
																				return example

													__UpperCamelCase							=dataset.remove_columns('''label'''				)
													__UpperCamelCase							=modified_dataset.map(UpperCamelCase__				)
													assert mapped_dataset.info.task_templates == []



