"""simple docstring"""







# using dfs for finding eulerian path traversal


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase=None			):






	"""simple docstring"""





	_lowercase :    List[str]							=							(path or []) + [u]
	for v in graph[u]:
		if visited_edge[u][v] is False:
			_lowercase				,      _lowercase :    Union[str, Any]							=							True, True
			_lowercase :    Any							=							dfs(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			)
	return path


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    List[str]							=							0
	_lowercase :    Union[str, Any]							=							-1
	for i in range(__UpperCAmelCase			):
		if i not in graph.keys():
			continue
		if len(graph[i]			) % 2 == 1:
			odd_degree_nodes += 1
			_lowercase :    Optional[int]							=							i
	if odd_degree_nodes == 0:
		return 1, odd_node
	if odd_degree_nodes == 2:
		return 2, odd_node
	return 3, odd_node


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Dict							=							[[False for _ in range(max_node + 1			)] for _ in range(max_node + 1			)]
	_lowercase				,      _lowercase :    List[str]							=							check_circuit_or_path(__UpperCAmelCase     ,__UpperCAmelCase			)
	if check == 3:
		print('graph is not Eulerian'			)
		print('no path'			)
		return
	_lowercase :    Any							=							1
	if check == 2:
		_lowercase :    List[str]							=							odd_node
		print('graph has a Euler path'			)
	if check == 1:
		print('graph has a Euler cycle'			)
	_lowercase :    Tuple							=							dfs(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			)
	print(__UpperCAmelCase			)


def      __lowerCAmelCase(		):






	"""simple docstring"""





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


if __name__ == "__main__":
						main()




"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    str							=							[0 for i in range(len(__UpperCAmelCase			)			)]

	# initialize interval's left pointer and right pointer
	_lowercase				,      _lowercase :    str							=							0, 0

	for i in range(1     ,len(__UpperCAmelCase			)			):
		# case when current index is inside the interval
		if i <= right_pointer:
			_lowercase :    Union[str, Any]							=							min(right_pointer - i + 1     ,z_result[i - left_pointer]			)
			_lowercase :    Any							=							min_edge

		while go_next(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):
			z_result[i] += 1

		# if new index's result gives us more right interval,
		# we've to update left_pointer and right_pointer
		if i + z_result[i] - 1 > right_pointer:
			_lowercase				,      _lowercase :    Optional[int]							=							i, i + z_result[i] - 1

	return z_result


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	return i + z_result[i] < len(__UpperCAmelCase			) and s[z_result[i]] == s[i + z_result[i]]


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Union[str, Any]							=							0
	# concatenate 'pattern' and 'input_str' and call z_function
	# with concatenated string
	_lowercase :    List[str]							=							z_function(pattern + input_str			)

	for val in z_result:
		# if value is greater then length of the pattern string
		# that means this index is starting position of substring
		# which is equal to pattern string
		if val >= len(__UpperCAmelCase			):
			answer += 1

	return answer


if __name__ == "__main__":
						import doctest

						doctest.testmod()



