

'''simple docstring'''

from collections import deque





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					return input(__magic_name__							).strip().split(" "							)





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							dict[int, list[int]]        =       {}
					for i in range(__magic_name__							):
										UpperCAmelCase		:							str        =       []

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





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							dict[int, list[int]]        =       {}
					for i in range(__magic_name__							):
										UpperCAmelCase		:							List[str]        =       []

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





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							dict[int, list[tuple[int, int]]]        =       {}
					for i in range(__magic_name__							):
										UpperCAmelCase		:							Tuple        =       []

					for e in range(__magic_name__							):
										UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase		:							str        =       (int(__magic_name__							) 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       :      str  	=			(int(i) for i in _input("Number of nodes and edges: "))

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

				a       :      Union[str, Any]  	=			{
				    1: initialize_unweighted_directed_graph,
				    2: initialize_unweighted_undirected_graph,
				    3: initialize_weighted_undirected_graph,
				}[graph_choice](n, m)





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







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





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







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





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase		:							List[Any]        =       {s: 0}, set(), {s: 0}
					while True:
										if len(__magic_name__							) == len(__magic_name__							) - 1:
															break
										UpperCAmelCase		:							Dict        =       10_0000
										for i in dist:
															if i not in known and dist[i] < mini:
																				UpperCAmelCase		:							Dict        =       dist[i]
																				UpperCAmelCase		:							int        =       i
										known.add(__magic_name__							)
										for v in g[u]:
															if v[0] not in known and dist[u] + v[1] < dist.get(v[0]			,   10_0000							):
																				UpperCAmelCase		:							int        =       dist[u] + v[1]
																				UpperCAmelCase		:							Optional[Any]        =       u
					for i in dist:
										if i != s:
															print(dist[i]							)





def 				lowercase (					__magic_name__			,   __magic_name__=None			,   __magic_name__=None							):



					'''simple docstring'''







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





def 				lowercase (					):



					'''simple docstring'''







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





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					((UpperCAmelCase) ,			(UpperCAmelCase))		:							Union[str, Any]        =       a_and_n
					UpperCAmelCase		:							Optional[int]        =       list(__magic_name__							)
					UpperCAmelCase		:							List[str]        =       [[0] * n for i in range(__magic_name__							)]
					for k in range(__magic_name__							):
										for i in range(__magic_name__							):
															for j in range(__magic_name__							):
																				if dist[i][j] > dist[i][k] + dist[k][j]:
																									UpperCAmelCase		:							Any        =       dist[i][k] + dist[k][j]
																									UpperCAmelCase		:							str        =       k
					print(__magic_name__							)





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase		:							int        =       {s: 0}, set(), {s: 0}
					while True:
										if len(__magic_name__							) == len(__magic_name__							) - 1:
															break
										UpperCAmelCase		:							Optional[Any]        =       10_0000
										for i in dist:
															if i not in known and dist[i] < mini:
																				UpperCAmelCase		:							Dict        =       dist[i]
																				UpperCAmelCase		:							Dict        =       i
										known.add(__magic_name__							)
										for v in g[u]:
															if v[0] not in known and v[1] < dist.get(v[0]			,   10_0000							):
																				UpperCAmelCase		:							List[str]        =       v[1]
																				UpperCAmelCase		:							Optional[Any]        =       u
					return dist





def 				lowercase (					):



					'''simple docstring'''







					UpperCAmelCase ,			UpperCAmelCase		:							Optional[Any]        =       map(__magic_name__			,   input().split(" "							)							)
					UpperCAmelCase		:							List[Any]        =       []
					for _ in range(__magic_name__							):
										edges.append(map(__magic_name__			,   input().split(" "							)							)							)
					return edges, n





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







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





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							Optional[int]        =       []
					for node in graph:
										if not graph[node]:
															isolated.append(__magic_name__							)
					return isolated



'''simple docstring'''

import multiprocessing
import os
from typing import BinaryIO, Optional, Union

from .. import Dataset, Features, NamedSplit, config
from ..formatting import query_table
from ..packaged_modules.csv.csv import Csv
from ..utils import logging
from ..utils.typing import NestedDataStructureLike, PathLike
from .abc import AbstractDatasetReader







class   UpperCamelCase__   (       lowercase__       ):


		"""simple docstring"""

		def __init__(			self   ,      snake_case   ,      snake_case = None   ,      snake_case = None   ,      snake_case = None   ,      snake_case = False   ,      snake_case = False   ,      snake_case = None   ,      **snake_case   ,      ):


							'''simple docstring'''

							super().__init__(
							    snake_case   ,      split=snake_case   ,      features=snake_case   ,      cache_dir=snake_case   ,      keep_in_memory=snake_case   ,      streaming=snake_case   ,      num_proc=snake_case   ,      **snake_case   ,      )
							UpperCAmelCase		:							str        =       path_or_paths if isinstance(snake_case   ,      snake_case      ) else {self.split: path_or_paths}
							UpperCAmelCase		:							int        =       Csv(
							    cache_dir=snake_case   ,      data_files=snake_case   ,      features=snake_case   ,      **snake_case   ,      )







		def 				A_	(			self      ):


							'''simple docstring'''

							if self.streaming:
												UpperCAmelCase		:							Optional[Any]        =       self.builder.as_streaming_dataset(split=self.split      )
							# Build regular (map-style) dataset
							else:
												UpperCAmelCase		:							Union[str, Any]        =       None
												UpperCAmelCase		:							str        =       None
												UpperCAmelCase		:							Union[str, Any]        =       None
												UpperCAmelCase		:							int        =       None

												self.builder.download_and_prepare(
												    download_config=snake_case   ,      download_mode=snake_case   ,      verification_mode=snake_case   ,      base_path=snake_case   ,      num_proc=self.num_proc   ,      )
												UpperCAmelCase		:							Tuple        =       self.builder.as_dataset(
												    split=self.split   ,      verification_mode=snake_case   ,      in_memory=self.keep_in_memory      )
							return dataset







class   UpperCamelCase__   :


		"""simple docstring"""

		def __init__(			self   ,      snake_case   ,      snake_case   ,      snake_case = None   ,      snake_case = None   ,      **snake_case   ,      ):


							'''simple docstring'''

							if num_proc is not None and num_proc <= 0:
												raise ValueError(f"num_proc {num_proc} must be an integer > 0."      )

							UpperCAmelCase		:							Tuple        =       dataset
							UpperCAmelCase		:							Dict        =       path_or_buf
							UpperCAmelCase		:							List[Any]        =       batch_size if batch_size else config.DEFAULT_MAX_BATCH_SIZE
							UpperCAmelCase		:							str        =       num_proc
							UpperCAmelCase		:							List[Any]        =       "utf-8"
							UpperCAmelCase		:							Tuple        =       to_csv_kwargs







		def 				A_	(			self      ):


							'''simple docstring'''

							UpperCAmelCase		:							List[str]        =       self.to_csv_kwargs.pop("path_or_buf"   ,      snake_case      )
							UpperCAmelCase		:							Any        =       self.to_csv_kwargs.pop("header"   ,      snake_case      )
							UpperCAmelCase		:							Dict        =       self.to_csv_kwargs.pop("index"   ,      snake_case      )

							if isinstance(self.path_or_buf   ,      (str, bytes, os.PathLike)      ):
												with open(self.path_or_buf   ,      "wb+"      ) as buffer:
																	UpperCAmelCase		:							Tuple        =       self._write(file_obj=snake_case   ,      header=snake_case   ,      index=snake_case   ,      **self.to_csv_kwargs      )
							else:
												UpperCAmelCase		:							Any        =       self._write(file_obj=self.path_or_buf   ,      header=snake_case   ,      index=snake_case   ,      **self.to_csv_kwargs      )
							return written







		def 				A_	(			self   ,      snake_case      ):


							'''simple docstring'''

							UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase		:							Optional[int]        =       args

							UpperCAmelCase		:							List[str]        =       query_table(
							    table=self.dataset.data   ,      key=slice(snake_case   ,      offset + self.batch_size      )   ,      indices=self.dataset._indices   ,      )
							UpperCAmelCase		:							int        =       batch.to_pandas().to_csv(
							    path_or_buf=snake_case   ,      header=header if (offset == 0) else False   ,      index=snake_case   ,      **snake_case      )
							return csv_str.encode(self.encoding      )







		def 				A_	(			self   ,      snake_case   ,      snake_case   ,      snake_case   ,      **snake_case      ):


							'''simple docstring'''

							UpperCAmelCase		:							List[str]        =       0

							if self.num_proc is None or self.num_proc == 1:
												for offset in logging.tqdm(
												    range(0   ,      len(self.dataset      )   ,      self.batch_size      )   ,      unit="ba"   ,      disable=not logging.is_progress_bar_enabled()   ,      desc="Creating CSV from Arrow format"   ,      ):
																	UpperCAmelCase		:							Any        =       self._batch_csv((offset, header, index, to_csv_kwargs)      )
																	written += file_obj.write(snake_case      )

							else:
												UpperCAmelCase ,			UpperCAmelCase		:							Union[str, Any]        =       len(self.dataset      ), self.batch_size
												with multiprocessing.Pool(self.num_proc      ) as pool:
																	for csv_str in logging.tqdm(
																	    pool.imap(
																	        self._batch_csv   ,      [(offset, header, index, to_csv_kwargs) for offset in range(0   ,      snake_case   ,      snake_case      )]   ,      )   ,      total=(num_rows // batch_size) + 1 if num_rows % batch_size else num_rows // batch_size   ,      unit="ba"   ,      disable=not logging.is_progress_bar_enabled()   ,      desc="Creating CSV from Arrow format"   ,      ):
																						written += file_obj.write(snake_case      )

							return written
