




"""simple docstring"""

from typing import Dict

from transformers import EvalPrediction, HfArgumentParser, TrainingArguments, is_torch_available
from transformers.testing_utils import (
    TestCasePlus,
    execute_subprocess_async,
    get_torch_dist_unique_port,
    require_torch_multi_gpu,
    require_torch_neuroncore,
)
from transformers.training_args import ParallelMode
from transformers.utils import logging


_lowerCamelCase  :			str        =       logging.get_logger(__name__)


if is_torch_available():
		import torch
		from torch import nn
		from torch.utils.data import Dataset

		from transformers import Trainer

		class        lowercase      (    __UpperCAmelCase):







						def __init__(							self   :					List[Any]      ,     _lowerCamelCase   :					int = 1_01       ):



							"""simple docstring"""

							A_  :				Any	   =		length







						def __len__(							self   :					str       ):



							"""simple docstring"""

							return self.length







						def __getitem__(							self   :					Any      ,     _lowerCamelCase   :					List[Any]       ):



							"""simple docstring"""

							return i

		class        lowercase      :







						def __call__(							self   :					int      ,     _lowerCamelCase   :					Union[str, Any]       ):



							"""simple docstring"""

							return {"input_ids": torch.tensor(_lowerCamelCase       ), "labels": torch.tensor(_lowerCamelCase       )}

		class        lowercase      (    nn.Module):







						def __init__(							self   :					Tuple       ):



							"""simple docstring"""

							super().__init__()
							# Add some (unused) params otherwise DDP will complain.
							A_  :				Tuple	   =		nn.Linear(1_20      ,     80       )







						def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Any=None       ):



							"""simple docstring"""

							if labels is not None:
								return torch.tensor(0.0      ,     device=input_ids.device       ), input_ids
							else:
								return input_ids

class        lowercase      (    __UpperCAmelCase):







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



					"""simple docstring"""

					A_  :				int	   =		F"""--nproc_per_node=2
            --master_port={get_torch_dist_unique_port()}
            {self.test_file_dir}/test_trainer_distributed.py
        """.split()
					A_  :				Optional[int]	   =		self.get_auto_remove_tmp_dir()
					A_  :				List[str]	   =		F"""--output_dir {output_dir}""".split()
					A_  :				Dict	   =		['''torchrun'''] + distributed_args + args
					execute_subprocess_async(_lowerCamelCase      ,     env=self.get_env()       )
					# successful return here == success - any errors would have caused an error in the sub-call

class        lowercase      (    __UpperCAmelCase):







				@require_torch_multi_gpu
				def 					a_  (							self   :					Optional[Any]       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		F"""--nproc_per_node={torch.cuda.device_count()}
            --master_port={get_torch_dist_unique_port()}
            {self.test_file_dir}/test_trainer_distributed.py
        """.split()
					A_  :				Union[str, Any]	   =		self.get_auto_remove_tmp_dir()
					A_  :				List[str]	   =		F"""--output_dir {output_dir}""".split()
					A_  :				List[Any]	   =		['''torchrun'''] + distributed_args + args
					execute_subprocess_async(_lowerCamelCase      ,     env=self.get_env()       )
					# successful return here == success - any errors would have caused an error in the sub-call


if __name__ == "__main__":
		# The script below is meant to be run under torch.distributed, on a machine with multiple GPUs:
		#
		# PYTHONPATH="src" python -m torch.distributed.run --nproc_per_node 2 --output_dir output_dir ./tests/test_trainer_distributed.py

		_lowerCamelCase  :			Optional[int]        =       HfArgumentParser((TrainingArguments,))
		_lowerCamelCase  :			List[str]        =       parser.parse_args_into_dataclasses()[0]

		logger.warning(
		    f'Process rank: {training_args.local_rank}, device: {training_args.device}, n_gpu: {training_args.n_gpu}, '
		    f'distributed training: {training_args.parallel_mode != ParallelMode.NOT_DISTRIBUTED}'
		)

		# Essentially, what we want to verify in the distributed case is that we get all samples back,
		# in the right order. (this is crucial for prediction for instance)
		for dataset_length in [101, 40, 7]:
				_lowerCamelCase  :			Tuple        =       DummyDataset(dataset_length)

				def 		lowercase_      (		_UpperCAmelCase	):




					"""simple docstring"""






					A_  :				int	   =		list(range(len(_UpperCAmelCase	)	)	)
					A_  :				List[str]	   =		p.predictions.tolist() == sequential and p.label_ids.tolist() == sequential
					if not success and training_args.local_rank == 0:
						logger.warning(
						    '''Predictions and/or labels do not match expected results:\n  - predictions: '''
						    f"""{p.predictions.tolist()}\n  - labels: {p.label_ids.tolist()}\n  - expected: {sequential}"""	)
					return {"success": success}

				_lowerCamelCase  :			List[str]        =       Trainer(
				    model=DummyModel(),
				    args=training_args,
				    data_collator=DummyDataCollator(),
				    eval_dataset=dataset,
				    compute_metrics=compute_metrics,
				)
				_lowerCamelCase  :			Optional[Any]        =       trainer.evaluate()
				logger.info(metrics)
				if metrics["eval_success"] is not True:
						logger.error(metrics)
						exit(1)

				_lowerCamelCase  :			int        =       trainer.predict(dataset)
				logger.info(p.metrics)
				if p.metrics["test_success"] is not True:
						logger.error(p.metrics)
						exit(1)

				_lowerCamelCase  :			Any        =       2

				_lowerCamelCase  :			Tuple        =       trainer.evaluate()
				logger.info(metrics)
				if metrics["eval_success"] is not True:
						logger.error(metrics)
						exit(1)

				_lowerCamelCase  :			Dict        =       trainer.predict(dataset)
				logger.info(p.metrics)
				if p.metrics["test_success"] is not True:
						logger.error(p.metrics)
						exit(1)
				_lowerCamelCase  :			Any        =       None











"""simple docstring"""

from collections import deque
from math import floor
from random import random
from time import time

class        lowercase      :







				def __init__(							self   :					Dict       ):



					"""simple docstring"""

					A_  :				Tuple	   =		{}







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					List[Any]      ,     _lowerCamelCase   :					Dict      ,     _lowerCamelCase   :					List[Any]=1       ):



					"""simple docstring"""

					if self.graph.get(_lowerCamelCase       ):
						if self.graph[u].count([w, v]       ) == 0:
							self.graph[u].append([w, v]       )
					else:
						A_  :				int	   =		[[w, v]]
					if not self.graph.get(_lowerCamelCase       ):
						A_  :				List[Any]	   =		[]







				def 					a_  (							self   :					Optional[int]       ):



					"""simple docstring"""

					return list(self.graph       )







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					str      ,     _lowerCamelCase   :					Tuple       ):



					"""simple docstring"""

					if self.graph.get(_lowerCamelCase       ):
						for _ in self.graph[u]:
							if _[1] == v:
								self.graph[u].remove(_lowerCamelCase       )







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					Optional[int]=-2      ,     _lowerCamelCase   :					Tuple=-1       ):



					"""simple docstring"""

					if s == d:
						return []
					A_  :				Union[str, Any]	   =		[]
					A_  :				Optional[int]	   =		[]
					if s == -2:
						A_  :				int	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				Tuple	   =		s

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Optional[Any]	   =		s
							for node in self.graph[s]:
								if visited.count(node[1]       ) < 1:
									if node[1] == d:
										visited.append(_lowerCamelCase       )
										return visited
									else:
										stack.append(node[1]       )
										visited.append(node[1]       )
										A_  :				Union[str, Any]	   =		node[1]
										break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							if len(_lowerCamelCase       ) != 0:
								A_  :				Optional[int]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				List[Any]	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return visited







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					List[Any]=-1       ):



					"""simple docstring"""

					if c == -1:
						A_  :				List[Any]	   =		floor(random() * 1_00_00       ) + 10
					for i in range(_lowerCamelCase       ):
						# every vertex has max 100 edges
						for _ in range(floor(random() * 1_02       ) + 1       ):
							A_  :				Tuple	   =		floor(random() * c       ) + 1
							if n != i:
								self.add_pair(_lowerCamelCase      ,     _lowerCamelCase      ,     1       )







				def 					a_  (							self   :					Optional[int]      ,     _lowerCamelCase   :					Union[str, Any]=-2       ):



					"""simple docstring"""

					A_  :				List[str]	   =		deque()
					A_  :				int	   =		[]
					if s == -2:
						A_  :				Any	   =		list(self.graph       )[0]
					d.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					while d:
						A_  :				List[Any]	   =		d.popleft()
						if len(self.graph[s]       ) != 0:
							for node in self.graph[s]:
								if visited.count(node[1]       ) < 1:
									d.append(node[1]       )
									visited.append(node[1]       )
					return visited







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



					"""simple docstring"""

					A_  :				List[Any]	   =		0
					for x in self.graph:
						for y in self.graph[x]:
							if y[1] == u:
								count += 1
					return count







				def 					a_  (							self   :					Any      ,     _lowerCamelCase   :					Optional[Any]       ):



					"""simple docstring"""

					return len(self.graph[u]       )







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					Tuple=-2       ):



					"""simple docstring"""

					A_  :				int	   =		[]
					A_  :				Optional[Any]	   =		[]
					if s == -2:
						A_  :				List[str]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				str	   =		s
					A_  :				List[Any]	   =		[]

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				str	   =		s
							for node in self.graph[s]:
								if visited.count(node[1]       ) < 1:
									stack.append(node[1]       )
									visited.append(node[1]       )
									A_  :				List[Any]	   =		node[1]
									break

            # check if all the children are visited
						if s == ss:
							sorted_nodes.append(stack.pop()       )
							if len(_lowerCamelCase       ) != 0:
								A_  :				List[str]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				int	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return sorted_nodes







				def 					a_  (							self   :					Dict       ):



					"""simple docstring"""

					A_  :				str	   =		[]
					A_  :				Dict	   =		[]
					A_  :				Dict	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				Any	   =		-2
					A_  :				List[str]	   =		[]
					A_  :				Dict	   =		s
					A_  :				Tuple	   =		False
					A_  :				List[str]	   =		set()

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Dict	   =		s
							for node in self.graph[s]:
								if (
								    visited.count(node[1]       ) > 0
								    and node[1] != parent
								    and indirect_parents.count(node[1]       ) > 0
								    and not on_the_way_back
								):
									A_  :				Tuple	   =		len(_lowerCamelCase       ) - 1
									while len_stack >= 0:
										if stack[len_stack] == node[1]:
											anticipating_nodes.add(node[1]       )
											break
										else:
											anticipating_nodes.add(stack[len_stack]       )
											len_stack -= 1
								if visited.count(node[1]       ) < 1:
									stack.append(node[1]       )
									visited.append(node[1]       )
									A_  :				int	   =		node[1]
									break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							A_  :				Optional[int]	   =		True
							if len(_lowerCamelCase       ) != 0:
								A_  :				Union[str, Any]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				int	   =		False
							indirect_parents.append(_lowerCamelCase       )
							A_  :				Dict	   =		s
							A_  :				Optional[int]	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return list(_lowerCamelCase       )







				def 					a_  (							self   :					List[str]       ):



					"""simple docstring"""

					A_  :				Dict	   =		[]
					A_  :				Dict	   =		[]
					A_  :				Optional[Any]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				Optional[Any]	   =		-2
					A_  :				List[str]	   =		[]
					A_  :				List[Any]	   =		s
					A_  :				int	   =		False
					A_  :				Any	   =		set()

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Union[str, Any]	   =		s
							for node in self.graph[s]:
								if (
								    visited.count(node[1]       ) > 0
								    and node[1] != parent
								    and indirect_parents.count(node[1]       ) > 0
								    and not on_the_way_back
								):
									A_  :				Dict	   =		len(_lowerCamelCase       ) - 1
									while len_stack_minus_one >= 0:
										if stack[len_stack_minus_one] == node[1]:
											anticipating_nodes.add(node[1]       )
											break
										else:
											return True
								if visited.count(node[1]       ) < 1:
									stack.append(node[1]       )
									visited.append(node[1]       )
									A_  :				Any	   =		node[1]
									break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							A_  :				str	   =		True
							if len(_lowerCamelCase       ) != 0:
								A_  :				Optional[int]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				Tuple	   =		False
							indirect_parents.append(_lowerCamelCase       )
							A_  :				int	   =		s
							A_  :				List[Any]	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return False







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					Union[str, Any]=-2      ,     _lowerCamelCase   :					int=-1       ):



					"""simple docstring"""

					A_  :				int	   =		time()
					self.dfs(_lowerCamelCase      ,     _lowerCamelCase       )
					A_  :				int	   =		time()
					return end - begin







				def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					str=-2       ):



					"""simple docstring"""

					A_  :				int	   =		time()
					self.bfs(_lowerCamelCase       )
					A_  :				Union[str, Any]	   =		time()
					return end - begin

class        lowercase      :







				def __init__(							self   :					Any       ):



					"""simple docstring"""

					A_  :				Tuple	   =		{}







				def 					a_  (							self   :					List[Any]      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Optional[int]=1       ):



					"""simple docstring"""

					if self.graph.get(_lowerCamelCase       ):
						# if there already is a edge
						if self.graph[u].count([w, v]       ) == 0:
							self.graph[u].append([w, v]       )
					else:
						# if u does not exist
						A_  :				Union[str, Any]	   =		[[w, v]]
					# add the other way
					if self.graph.get(_lowerCamelCase       ):
						# if there already is a edge
						if self.graph[v].count([w, u]       ) == 0:
							self.graph[v].append([w, u]       )
					else:
						# if u does not exist
						A_  :				Tuple	   =		[[w, u]]







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Dict       ):



					"""simple docstring"""

					if self.graph.get(_lowerCamelCase       ):
						for _ in self.graph[u]:
							if _[1] == v:
								self.graph[u].remove(_lowerCamelCase       )
        # the other way round
					if self.graph.get(_lowerCamelCase       ):
						for _ in self.graph[v]:
							if _[1] == u:
								self.graph[v].remove(_lowerCamelCase       )







				def 					a_  (							self   :					Any      ,     _lowerCamelCase   :					str=-2      ,     _lowerCamelCase   :					int=-1       ):



					"""simple docstring"""

					if s == d:
						return []
					A_  :				Optional[Any]	   =		[]
					A_  :				List[Any]	   =		[]
					if s == -2:
						A_  :				Optional[int]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				Union[str, Any]	   =		s

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Any	   =		s
							for node in self.graph[s]:
								if visited.count(node[1]       ) < 1:
									if node[1] == d:
										visited.append(_lowerCamelCase       )
										return visited
									else:
										stack.append(node[1]       )
										visited.append(node[1]       )
										A_  :				int	   =		node[1]
										break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							if len(_lowerCamelCase       ) != 0:
								A_  :				List[Any]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				str	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return visited







				def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					Union[str, Any]=-1       ):



					"""simple docstring"""

					if c == -1:
						A_  :				List[Any]	   =		floor(random() * 1_00_00       ) + 10
					for i in range(_lowerCamelCase       ):
						# every vertex has max 100 edges
						for _ in range(floor(random() * 1_02       ) + 1       ):
							A_  :				List[str]	   =		floor(random() * c       ) + 1
							if n != i:
								self.add_pair(_lowerCamelCase      ,     _lowerCamelCase      ,     1       )







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					List[Any]=-2       ):



					"""simple docstring"""

					A_  :				Dict	   =		deque()
					A_  :				Tuple	   =		[]
					if s == -2:
						A_  :				List[str]	   =		list(self.graph       )[0]
					d.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					while d:
						A_  :				str	   =		d.popleft()
						if len(self.graph[s]       ) != 0:
							for node in self.graph[s]:
								if visited.count(node[1]       ) < 1:
									d.append(node[1]       )
									visited.append(node[1]       )
					return visited







				def 					a_  (							self   :					Any      ,     _lowerCamelCase   :					int       ):



					"""simple docstring"""

					return len(self.graph[u]       )







				def 					a_  (							self   :					Any       ):



					"""simple docstring"""

					A_  :				Dict	   =		[]
					A_  :				Optional[int]	   =		[]
					A_  :				Union[str, Any]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				str	   =		-2
					A_  :				int	   =		[]
					A_  :				Optional[Any]	   =		s
					A_  :				str	   =		False
					A_  :				int	   =		set()

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Tuple	   =		s
							for node in self.graph[s]:
								if (
								    visited.count(node[1]       ) > 0
								    and node[1] != parent
								    and indirect_parents.count(node[1]       ) > 0
								    and not on_the_way_back
								):
									A_  :				Tuple	   =		len(_lowerCamelCase       ) - 1
									while len_stack >= 0:
										if stack[len_stack] == node[1]:
											anticipating_nodes.add(node[1]       )
											break
										else:
											anticipating_nodes.add(stack[len_stack]       )
											len_stack -= 1
								if visited.count(node[1]       ) < 1:
									stack.append(node[1]       )
									visited.append(node[1]       )
									A_  :				str	   =		node[1]
									break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							A_  :				Union[str, Any]	   =		True
							if len(_lowerCamelCase       ) != 0:
								A_  :				Tuple	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				str	   =		False
							indirect_parents.append(_lowerCamelCase       )
							A_  :				Union[str, Any]	   =		s
							A_  :				List[str]	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return list(_lowerCamelCase       )







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



					"""simple docstring"""

					A_  :				List[str]	   =		[]
					A_  :				int	   =		[]
					A_  :				List[Any]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				int	   =		-2
					A_  :				Tuple	   =		[]
					A_  :				Any	   =		s
					A_  :				Tuple	   =		False
					A_  :				Union[str, Any]	   =		set()

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Any	   =		s
							for node in self.graph[s]:
								if (
								    visited.count(node[1]       ) > 0
								    and node[1] != parent
								    and indirect_parents.count(node[1]       ) > 0
								    and not on_the_way_back
								):
									A_  :				Optional[int]	   =		len(_lowerCamelCase       ) - 1
									while len_stack_minus_one >= 0:
										if stack[len_stack_minus_one] == node[1]:
											anticipating_nodes.add(node[1]       )
											break
										else:
											return True
								if visited.count(node[1]       ) < 1:
									stack.append(node[1]       )
									visited.append(node[1]       )
									A_  :				Optional[Any]	   =		node[1]
									break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							A_  :				Optional[int]	   =		True
							if len(_lowerCamelCase       ) != 0:
								A_  :				str	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				List[Any]	   =		False
							indirect_parents.append(_lowerCamelCase       )
							A_  :				List[Any]	   =		s
							A_  :				List[Any]	   =		ss

						# check if se have reached the starting point
						if len(_lowerCamelCase       ) == 0:
							return False







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



					"""simple docstring"""

					return list(self.graph       )







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					Union[str, Any]=-2      ,     _lowerCamelCase   :					str=-1       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		time()
					self.dfs(_lowerCamelCase      ,     _lowerCamelCase       )
					A_  :				Union[str, Any]	   =		time()
					return end - begin







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					str=-2       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		time()
					self.bfs(_lowerCamelCase       )
					A_  :				List[str]	   =		time()
					return end - begin





