






'''simple docstring'''


def 	__magic_name__( _A						,      _A					):
						'''simple docstring'''





						while b:
												UpperCamelCase__    ,   UpperCamelCase__         = b, a % b
						return a







def 	__magic_name__( _A						,      _A					):
						'''simple docstring'''





						return a if b == 0 else euclidean_gcd_recursive(_A						,      a % b					)







def 	__magic_name__( ):
						'''simple docstring'''





						print(f"euclidean_gcd(3, 5) = {euclidean_gcd(3						,      5					)}"					)
						print(f"euclidean_gcd(5, 3) = {euclidean_gcd(5						,      3					)}"					)
						print(f"euclidean_gcd(1, 3) = {euclidean_gcd(1						,      3					)}"					)
						print(f"euclidean_gcd(3, 6) = {euclidean_gcd(3						,      6					)}"					)
						print(f"euclidean_gcd(6, 3) = {euclidean_gcd(6						,      3					)}"					)

						print(f"euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3						,      5					)}"					)
						print(f"euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5						,      3					)}"					)
						print(f"euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1						,      3					)}"					)
						print(f"euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3						,      6					)}"					)
						print(f"euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6						,      3					)}"					)


if __name__ == "__main__":
					main()








'''simple docstring'''


from collections import defaultdict







def 	__magic_name__( _A					):
						'''simple docstring'''





						UpperCamelCase__         = 1
						UpperCamelCase__         = True
						for v in tree[start]:
												if v not in visited:
																		ret += dfs(_A					)
						if ret % 2 == 0:
												cuts.append(_A					)
						return ret







def 	__magic_name__( ):
						'''simple docstring'''





						dfs(1					)


if __name__ == "__main__":
					lowerCamelCase_	,     lowerCamelCase_				: int    	=							10, 9
					lowerCamelCase_				: int    	=							defaultdict(list)
					lowerCamelCase_				: dict[int, bool]    	=							{}
					lowerCamelCase_				: list[int]    	=							[]
					lowerCamelCase_				: Union[str, Any]    	=							0
					lowerCamelCase_				: Tuple    	=							[(2, 1), (3, 1), (4, 3), (5, 2), (6, 1), (7, 2), (8, 6), (9, 8), (10, 8)]
					for u, v in edges:
										tree[u].append(v)
										tree[v].append(u)
					even_tree()
					print(len(cuts) - 1)
