






# using dfs for finding eulerian path traversal

def    SCREAMING_SNAKE_CASE_							(							__magic_name__					:  str	,			__magic_name__					:  Union[str, Any]	,			__magic_name__					:  Any	,			__magic_name__					:  int=None					)		->			Union[str, Any]:






	"""simple docstring"""



	UpperCamelCase     :Any          =	(path or []) + [u]
	for v in graph[u]:
		if visited_edge[u][v] is False:
			UpperCamelCase     ,      UpperCamelCase     :Optional[Any]          =	True, True
			UpperCamelCase     :Dict          =	dfs(__magic_name__	,			__magic_name__	,			__magic_name__	,			__magic_name__					)
	return path

def    SCREAMING_SNAKE_CASE_							(							__magic_name__					:  List[Any]	,			__magic_name__					:  Optional[Any]					)		->			Dict:






	"""simple docstring"""



	UpperCamelCase     :Dict          =	0
	UpperCamelCase     :Dict          =	-1
	for i in range(__magic_name__					):
		if i not in graph.keys():
			continue
		if len(graph[i]					) % 2 == 1:
			odd_degree_nodes += 1
			UpperCamelCase     :List[Any]          =	i
	if odd_degree_nodes == 0:
		return 1, odd_node
	if odd_degree_nodes == 2:
		return 2, odd_node
	return 3, odd_node

def    SCREAMING_SNAKE_CASE_							(							__magic_name__					:  int	,			__magic_name__					:  List[Any]					)		->			int:






	"""simple docstring"""



	UpperCamelCase     :str          =	[[False for _ in range(max_node + 1					)] for _ in range(max_node + 1					)]
	UpperCamelCase     ,      UpperCamelCase     :Optional[int]          =	check_circuit_or_path(__magic_name__	,			__magic_name__					)
	if check == 3:
		print("""graph is not Eulerian"""					)
		print("""no path"""					)
		return
	UpperCamelCase     :int          =	1
	if check == 2:
		UpperCamelCase     :Optional[int]          =	odd_node
		print("""graph has a Euler path"""					)
	if check == 1:
		print("""graph has a Euler cycle"""					)
	UpperCamelCase     :Optional[int]          =	dfs(__magic_name__	,			__magic_name__	,			__magic_name__					)
	print(__magic_name__					)

def    SCREAMING_SNAKE_CASE_							(							)		->			List[Any]:






	"""simple docstring"""



	UpperCamelCase     :List[Any]          =	{1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
	UpperCamelCase     :Optional[int]          =	{1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
	UpperCamelCase     :Tuple          =	{1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
	UpperCamelCase     :Optional[Any]          =	{1: [2, 3], 2: [1, 3], 3: [1, 2]}
	UpperCamelCase     :List[Any]          =	{
	    1: [],
	    2: []
	    # all degree is zero
	}
	UpperCamelCase     :List[str]          =	10
	check_euler(__magic_name__	,			__magic_name__					)
	check_euler(__magic_name__	,			__magic_name__					)
	check_euler(__magic_name__	,			__magic_name__					)
	check_euler(__magic_name__	,			__magic_name__					)
	check_euler(__magic_name__	,			__magic_name__					)


if __name__ == "__main__":
	main()








import re
import string

import numpy as np

import datasets


UpperCAmelCase_ :						Dict      =      '''
Returns the rate at which the input predicted strings exactly match their references, ignoring any strings input as part of the regexes_to_ignore list.
'''

UpperCAmelCase_ :						Any      =      '''
Args:
    predictions: List of predicted texts.
    references: List of reference texts.
    regexes_to_ignore: List, defaults to None. Regex expressions of characters to
        ignore when calculating the exact matches. Note: these regexes are removed
        from the input data before the changes based on the options below (e.g. ignore_case,
        ignore_punctuation, ignore_numbers) are applied.
    ignore_case: Boolean, defaults to False. If true, turns everything
        to lowercase so that capitalization differences are ignored.
    ignore_punctuation: Boolean, defaults to False. If true, removes all punctuation before
        comparing predictions and references.
    ignore_numbers: Boolean, defaults to False. If true, removes all punctuation before
        comparing predictions and references.
Returns:
    exact_match: Dictionary containing exact_match rate. Possible values are between 0.0 and 100.0, inclusive.
Examples:
    >>> exact_match = datasets.load_metric("exact_match")
    >>> refs = ["the cat", "theater", "YELLING", "agent007"]
    >>> preds = ["cat?", "theater", "yelling", "agent"]
    >>> results = exact_match.compute(references=refs, predictions=preds)
    >>> print(round(results["exact_match"], 1))
    25.0

    >>> exact_match = datasets.load_metric("exact_match")
    >>> refs = ["the cat", "theater", "YELLING", "agent007"]
    >>> preds = ["cat?", "theater", "yelling", "agent"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell"], ignore_case=True, ignore_punctuation=True)
    >>> print(round(results["exact_match"], 1))
    50.0


    >>> exact_match = datasets.load_metric("exact_match")
    >>> refs = ["the cat", "theater", "YELLING", "agent007"]
    >>> preds = ["cat?", "theater", "yelling", "agent"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell", "YELL"], ignore_case=True, ignore_punctuation=True)
    >>> print(round(results["exact_match"], 1))
    75.0

    >>> exact_match = datasets.load_metric("exact_match")
    >>> refs = ["the cat", "theater", "YELLING", "agent007"]
    >>> preds = ["cat?", "theater", "yelling", "agent"]
    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell", "YELL"], ignore_case=True, ignore_punctuation=True, ignore_numbers=True)
    >>> print(round(results["exact_match"], 1))
    100.0

    >>> exact_match = datasets.load_metric("exact_match")
    >>> refs = ["The cat sat on the mat.", "Theaters are great.", "It\'s like comparing oranges and apples."]
    >>> preds = ["The cat sat on the mat?", "Theaters are great.", "It\'s like comparing apples and oranges."]
    >>> results = exact_match.compute(references=refs, predictions=preds)
    >>> print(round(results["exact_match"], 1))
    33.3

'''

UpperCAmelCase_ :						Tuple      =      '''
'''

@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION		,   _KWARGS_DESCRIPTION      )
class     _SCREAMING_SNAKE_CASE       (			datasets.Metric      ):





	def 						_A (		self				:					Optional[int]	):
		return datasets.MetricInfo(
		    description=_DESCRIPTION ,  citation=_CITATION ,  inputs_description=_KWARGS_DESCRIPTION ,  features=datasets.Features(
		        {
		            """predictions""": datasets.Value("""string""" ,  id="""sequence"""	),
		            """references""": datasets.Value("""string""" ,  id="""sequence"""	),
		        }	) ,  reference_urls=[] ,  )





	def 						_A (		self				:					Optional[int] ,  __lowerCamelCase				:					Union[str, Any] ,  __lowerCamelCase				:					List[str] ,  __lowerCamelCase				:					List[str]=None ,  __lowerCamelCase				:					Optional[int]=False ,  __lowerCamelCase				:					int=False ,  __lowerCamelCase				:					Optional[int]=False ,  ):
		if regexes_to_ignore is not None:
			for s in regexes_to_ignore:
				UpperCamelCase     :str          =	np.array([re.sub(__lowerCamelCase ,  """""" ,  __lowerCamelCase	) for x in predictions]	)
				UpperCamelCase     :Tuple          =	np.array([re.sub(__lowerCamelCase ,  """""" ,  __lowerCamelCase	) for x in references]	)
		else:
			UpperCamelCase     :Any          =	np.asarray(__lowerCamelCase	)
			UpperCamelCase     :str          =	np.asarray(__lowerCamelCase	)

		if ignore_case:
			UpperCamelCase     :Tuple          =	np.char.lower(__lowerCamelCase	)
			UpperCamelCase     :Any          =	np.char.lower(__lowerCamelCase	)

		if ignore_punctuation:
			UpperCamelCase     :Optional[int]          =	string.punctuation.maketrans("""""" ,  """""" ,  string.punctuation	)
			UpperCamelCase     :Optional[Any]          =	np.char.translate(__lowerCamelCase ,  table=__lowerCamelCase	)
			UpperCamelCase     :List[str]          =	np.char.translate(__lowerCamelCase ,  table=__lowerCamelCase	)

		if ignore_numbers:
			UpperCamelCase     :Tuple          =	string.digits.maketrans("""""" ,  """""" ,  string.digits	)
			UpperCamelCase     :Dict          =	np.char.translate(__lowerCamelCase ,  table=__lowerCamelCase	)
			UpperCamelCase     :Tuple          =	np.char.translate(__lowerCamelCase ,  table=__lowerCamelCase	)

		UpperCamelCase     :int          =	predictions == references

		return {"exact_match": np.mean(__lowerCamelCase	) * 100}
