


'''simple docstring'''

import csv
import json
import os

import datasets


# TODO: Add BibTeX citation
# Find for instance the citation on arxiv or on the dataset repo/website
__lowercase:		Tuple    						=  "\\n@InProceedings{huggingface:dataset,\ntitle = {A great new dataset},\nauthor={huggingface, Inc.\n},\nyear={2020}\n}\n"

# TODO: Add description of the dataset here
# You can copy an official description
__lowercase:		Optional[int]    						=  "\\nThis new dataset is designed to solve this great NLP task and is crafted with a lot of care.\n"

# TODO: Add a link to an official homepage for the dataset here
__lowercase:		List[str]    						=  ""

# TODO: Add the licence for the dataset here if you can find it
__lowercase:		List[Any]    						=  ""

# TODO: Add link to the official dataset URLs here
# The HuggingFace Datasets library doesn't host the datasets but only points to the original files.
# This can be an arbitrary nested dict/list of URLs (see below in `_split_generators` method)
__lowercase:		List[str]    						=  {
    "first_domain": "https://huggingface.co/great-new-dataset-first_domain.zip",
    "second_domain": "https://huggingface.co/great-new-dataset-second_domain.zip",
}







class 			UpperCAmelCase			(							datasets.GeneratorBasedBuilder):
 _lowerCamelCase			:       List[str]            =       datasets.Version('1.1.0')

 # This is an example of a dataset with multiple configurations.
 # If you don't want/need to define several sub-sets in your dataset,
 # just remove the BUILDER_CONFIG_CLASS and the BUILDER_CONFIGS attributes.

 # If you need to make complex sub-parts in the datasets with configurable options
 # You can create your own builder configuration class to store attribute, inheriting from datasets.BuilderConfig
 # BUILDER_CONFIG_CLASS = MyBuilderConfig

 # You will be able to load one or the other configurations in the following list with
 # data = datasets.load_dataset('my_dataset', 'first_domain')
 # data = datasets.load_dataset('my_dataset', 'second_domain')
 _lowerCamelCase			:       Dict            =       [
     datasets.BuilderConfig(name='first_domain'		,      version=SCREAMING_SNAKE_CASE__		,      description='This part of my dataset covers a first domain'),
     datasets.BuilderConfig(name='second_domain'		,      version=SCREAMING_SNAKE_CASE__		,      description='This part of my dataset covers a second domain'),
 ]

 _lowerCamelCase			:       Any            =       'first_domain'  # It's not mandatory to have a default configuration. Just use one if it make sense.

 def 		lowercase_    (			self			:						List[str]       ):





    """simple docstring"""



    if self.config.name == "first_domain":  # This is the name of the configuration selected in BUILDER_CONFIGS above
       UpperCamelCase__			    =    datasets.Features(
           {
               "sentence": datasets.Value("string"       ),
               "option1": datasets.Value("string"       ),
               "answer": datasets.Value("string"       )
               # These are the features of your dataset like images, labels ...
           }       )
    else:  # This is an example to show how to have different features for "first_domain" and "second_domain"
       UpperCamelCase__			    =    datasets.Features(
           {
               "sentence": datasets.Value("string"       ),
               "option2": datasets.Value("string"       ),
               "second_domain_answer": datasets.Value("string"       )
               # These are the features of your dataset like images, labels ...
           }       )
    return datasets.DatasetInfo(
        # This is the description that will appear on the datasets page.
        description=_DESCRIPTION,       features=a_,       homepage=_HOMEPAGE,       license=_LICENSE,       citation=_CITATION,       )

 def 		lowercase_    (			self			:						Any,       a_			:						Union[str, Any]       ):





    """simple docstring"""



    UpperCamelCase__			    =    _URLS[self.config.name]
    UpperCamelCase__			    =    dl_manager.download_and_extract(a_       )
    return [
        datasets.SplitGenerator(
            name=datasets.Split.TRAIN,       gen_kwargs={
                "filepath": os.path.join(a_,       "train.jsonl"       ),
                "split": "train",
            },       ),
        datasets.SplitGenerator(
            name=datasets.Split.VALIDATION,       gen_kwargs={
                "filepath": os.path.join(a_,       "dev.jsonl"       ),
                "split": "dev",
            },       ),
        datasets.SplitGenerator(
            name=datasets.Split.TEST,       gen_kwargs={
                "filepath": os.path.join(a_,       "test.jsonl"       ),
                "split": "test"
            },       ),
    ]

 def 		lowercase_    (			self			:						str,       a_			:						Optional[Any],       a_			:						Tuple       ):





    """simple docstring"""



    with open(a_,       encoding="utf-8"       ) as f:
       for key, row in enumerate(a_       ):
          UpperCamelCase__			    =    json.loads(a_       )
          if self.config.name == "first_domain":
             # Yields examples as (key, example) tuples
             yield key, {
                 "sentence": data["sentence"],
                 "option1": data["option1"],
                 "answer": "" if split == "test" else data["answer"],
             }
          else:
             yield key, {
                 "sentence": data["sentence"],
                 "option2": data["option2"],
                 "second_domain_answer": "" if split == "test" else data["second_domain_answer"],
             }






from collections import deque
def  __UpperCamelCase    (						snake_case      )    ->		List[str]:


   '''simple docstring'''







   return input(snake_case      ).strip().split(''' '''      )
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		dict[int, list[int]]:


   '''simple docstring'''







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

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


   '''simple docstring'''







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

   for e in range(snake_case      ):
      __A   ,		__A    =  (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  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		dict[int, list[tuple[int, int]]]:


   '''simple docstring'''







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

   for e in range(snake_case      ):
      __A   ,		__A   ,		__A    =  (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__":
    _UpperCamelCase       ,    _UpperCamelCase       :				List[Any]           =			(int(i) for i in _input("""Number of nodes and edges: """))

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

    _UpperCamelCase       :				Optional[Any]           =			{
        1: initialize_unweighted_directed_graph,
        2: initialize_unweighted_undirected_graph,
        3: initialize_weighted_undirected_graph,
    }[graph_choice](n, m)
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		int:


   '''simple docstring'''







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


   '''simple docstring'''







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


   '''simple docstring'''







   __A   ,		__A   ,		__A    =  {s: 0}, set(), {s: 0}
   while True:
      if len(snake_case      ) == len(snake_case      ) - 1:
         break
      __A    =  1_0_0_0_0_0
      for i in dist:
         if i not in known and dist[i] < mini:
            __A    =  dist[i]
            __A    =  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]							,			1_0_0_0_0_0      ):
            __A    =  dist[u] + v[1]
            __A    =  u
   for i in dist:
      if i != s:
         print(dist[i]      )
def  __UpperCamelCase    (						snake_case							,			snake_case=None							,			snake_case=None      )    ->		Any:


   '''simple docstring'''







   if q is None:
      __A    =  [1]
   if ind is None:
      __A    =  [0] * (len(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(snake_case      )
   if len(snake_case      ) == 0:
      return
   __A    =  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  __UpperCamelCase    (						)    ->		Any:


   '''simple docstring'''







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


   '''simple docstring'''







   ((__A)   ,		(__A))    =  a_and_n
   __A    =  list(snake_case      )
   __A    =  [[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]:
               __A    =  dist[i][k] + dist[k][j]
               __A    =  k
   print(snake_case      )
def  __UpperCamelCase    (						snake_case							,			snake_case      )    ->		Dict:


   '''simple docstring'''







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


   '''simple docstring'''







   __A   ,		__A    =  map(snake_case							,			input().split(''' '''      )      )
   __A    =  []
   for _ in range(snake_case      ):
      edges.append(map(snake_case							,			input().split(''' '''      )      )      )
   return edges, n
def  __UpperCamelCase    (						snake_case      )    ->		int:


   '''simple docstring'''







   ((__A)   ,		(__A))    =  e_and_n
   e.sort(reverse=snake_case							,			key=lambda snake_case      : x[2]      )
   __A    =  [{i} for i in range(1							,			n + 1      )]
   while True:
      if len(snake_case      ) == 1:
         break
      print(snake_case      )
      __A    =  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  __UpperCamelCase    (						snake_case      )    ->		Tuple:


   '''simple docstring'''







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

