

"""simple docstring"""



import functools





def  _snake_case     (    UpperCAmelCase_  :					str					,   UpperCAmelCase_  :					Dict			):






					if not isinstance(UpperCamelCase__					,   UpperCamelCase__			) or not all(isinstance(UpperCamelCase__					,   UpperCamelCase__			) for day in days			):
										raise ValueError("""The parameter days should be a list of integers"""			)

					if len(UpperCamelCase__			) != 3 or not all(isinstance(UpperCamelCase__					,   UpperCamelCase__			) for cost in costs			):
										raise ValueError("""The parameter costs should be a list of three integers"""			)

					if len(UpperCamelCase__			) == 0:
										return 0

					if min(UpperCamelCase__			) <= 0:
										raise ValueError("""All days elements should be greater than 0"""			)

					if max(UpperCamelCase__			) >= 366:
										raise ValueError("""All days elements should be less than 366"""			)

					A__										=  set(UpperCamelCase__			)

					@functools.cache
					def dynamic_programming(UpperCAmelCase_  :					Optional[int]			) -> int:
										if index > 365:
															return 0

										if index not in days_set:
															return dynamic_programming(index + 1			)

										return min(
										    costs[0] + dynamic_programming(index + 1			)					,   costs[1] + dynamic_programming(index + 7			)					,   costs[2] + dynamic_programming(index + 30			)					,   )

					return dynamic_programming(1			)


if __name__ == "__main__":
	import doctest

	doctest.testmod()









"""simple docstring"""



from collections import defaultdict





def  _snake_case     (    UpperCAmelCase_  :					int			):
     A__										=  1
     A__										=  True
     for v in tree[start]:
          if v not in visited:
               ret += dfs(UpperCAmelCase_			)
     if ret % 2 == 0:
          cuts.append(UpperCAmelCase_			)
     return ret





def  _snake_case     (    ):
     dfs(1			)


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






