

"""simple docstring"""



from __future__ import annotations

import math
import random
from typing import Any



class 					a						:



				"""simple docstring"""



				def __init__(     self: List[Any]       ):






									"""simple docstring"""


									A__										=  []
									A__										=  0
									A__										=  0

				def 				UpperCamelCase	(     self: Tuple       ):






									"""simple docstring"""


									return self.head == self.tail

				def 				UpperCamelCase	(     self: List[str]    ,						UpperCamelCase: Any       ):






									"""simple docstring"""


									self.data.append(UpperCamelCase       )
									A__										=  self.tail + 1

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






									"""simple docstring"""


									A__										=  self.data[self.head]
									A__										=  self.head + 1
									return ret

				def 				UpperCamelCase	(     self: Optional[Any]       ):






									"""simple docstring"""


									return self.tail - self.head





				def 				UpperCamelCase	(     self: Tuple       ):






									"""simple docstring"""


									print(self.data       )
									print("""**************"""       )
									print(self.data[self.head : self.tail]       )



class 					a						:



				"""simple docstring"""



				def __init__(     self: Any    ,						UpperCamelCase: Any       ):






									"""simple docstring"""


									A__										=  data
									A__										=  None
									A__										=  None
									A__										=  1

				def 				UpperCamelCase	(     self: List[str]       ):






									"""simple docstring"""


									return self.data

				def 				UpperCamelCase	(     self: Dict       ):






									"""simple docstring"""


									return self.left

				def 				UpperCamelCase	(     self: int       ):






									"""simple docstring"""


									return self.right

				def 				UpperCamelCase	(     self: Optional[Any]       ):






									"""simple docstring"""


									return self.height

				def 				UpperCamelCase	(     self: Any    ,						UpperCamelCase: Any       ):






									"""simple docstring"""


									A__										=  data

				def 				UpperCamelCase	(     self: str    ,						UpperCamelCase: MyNode | None       ):






									"""simple docstring"""


									A__										=  node

				def 				UpperCamelCase	(     self: Optional[Any]    ,						UpperCamelCase: MyNode | None       ):






									"""simple docstring"""


									A__										=  node





				def 				UpperCamelCase	(     self: List[str]    ,						UpperCamelCase: int       ):






									"""simple docstring"""


									A__										=  height





def  _snake_case     (    UpperCAmelCase_  :					MyNode | None			):
					if node is None:
										return 0
					return node.get_height()





def  _snake_case     (    UpperCAmelCase_  :					int					,   UpperCAmelCase_  :					int			):
					if a > b:
										return a
					return b





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					print("""left rotation node:"""					,   node.get_data()			)
					A__										=  node.get_left()
					assert ret is not None
					node.set_left(ret.get_right()			)
					ret.set_right(UpperCAmelCase_			)
					A__										=  my_max(get_height(node.get_right()			)					,   get_height(node.get_left()			)			) + 1
					node.set_height(UpperCAmelCase_			)
					A__										=  my_max(get_height(ret.get_right()			)					,   get_height(ret.get_left()			)			) + 1
					ret.set_height(UpperCAmelCase_			)
					return ret





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					print("""right rotation node:"""					,   node.get_data()			)
					A__										=  node.get_right()
					assert ret is not None
					node.set_right(ret.get_left()			)
					ret.set_left(UpperCAmelCase_			)
					A__										=  my_max(get_height(node.get_right()			)					,   get_height(node.get_left()			)			) + 1
					node.set_height(UpperCAmelCase_			)
					A__										=  my_max(get_height(ret.get_right()			)					,   get_height(ret.get_left()			)			) + 1
					ret.set_height(UpperCAmelCase_			)
					return ret





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					A__										=  node.get_left()
					assert left_child is not None
					node.set_left(left_rotation(UpperCAmelCase_			)			)
					return right_rotation(UpperCAmelCase_			)





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					A__										=  node.get_right()
					assert right_child is not None
					node.set_right(right_rotation(UpperCAmelCase_			)			)
					return left_rotation(UpperCAmelCase_			)





def  _snake_case     (    UpperCAmelCase_  :					MyNode | None					,   UpperCAmelCase_  :					Any			):
					if node is None:
										return MyNode(UpperCAmelCase_			)
					if data < node.get_data():
										node.set_left(insert_node(node.get_left()					,   UpperCAmelCase_			)			)
										if (
										    get_height(node.get_left()			) - get_height(node.get_right()			) == 2
										):  # an unbalance detected
															A__										=  node.get_left()
															assert left_child is not None
															if (
															    data < left_child.get_data()
															):  # new node is the left child of the left child
																				A__										=  right_rotation(UpperCAmelCase_			)
															else:
																				A__										=  lr_rotation(UpperCAmelCase_			)
					else:
										node.set_right(insert_node(node.get_right()					,   UpperCAmelCase_			)			)
										if get_height(node.get_right()			) - get_height(node.get_left()			) == 2:
															A__										=  node.get_right()
															assert right_child is not None
															if data < right_child.get_data():
																				A__										=  rl_rotation(UpperCAmelCase_			)
															else:
																				A__										=  left_rotation(UpperCAmelCase_			)
					A__										=  my_max(get_height(node.get_right()			)					,   get_height(node.get_left()			)			) + 1
					node.set_height(UpperCAmelCase_			)
					return node





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					while True:
										A__										=  root.get_right()
										if right_child is None:
															break
										A__										=  right_child
					return root.get_data()





def  _snake_case     (    UpperCAmelCase_  :					MyNode			):
					while True:
										A__										=  root.get_left()
										if left_child is None:
															break
										A__										=  left_child
					return root.get_data()





def  _snake_case     (    UpperCAmelCase_  :					MyNode					,   UpperCAmelCase_  :					Any			):
					A__										=  root.get_left()
					A__										=  root.get_right()
					if root.get_data() == data:
										if left_child is not None and right_child is not None:
															A__										=  get_left_most(UpperCAmelCase_			)
															root.set_data(UpperCAmelCase_			)
															root.set_right(del_node(UpperCAmelCase_					,   UpperCAmelCase_			)			)
										elif left_child is not None:
															A__										=  left_child
										elif right_child is not None:
															A__										=  right_child
										else:
															return None
					elif root.get_data() > data:
										if left_child is None:
															print("""No such data"""			)
															return root
										else:
															root.set_left(del_node(UpperCAmelCase_					,   UpperCAmelCase_			)			)
					else:  # root.get_data() < data
										if right_child is None:
															return root
										else:
															root.set_right(del_node(UpperCAmelCase_					,   UpperCAmelCase_			)			)

					if get_height(UpperCAmelCase_			) - get_height(UpperCAmelCase_			) == 2:
										assert right_child is not None
										if get_height(right_child.get_right()			) > get_height(right_child.get_left()			):
															A__										=  left_rotation(UpperCAmelCase_			)
										else:
															A__										=  rl_rotation(UpperCAmelCase_			)
					elif get_height(UpperCAmelCase_			) - get_height(UpperCAmelCase_			) == -2:
										assert left_child is not None
										if get_height(left_child.get_left()			) > get_height(left_child.get_right()			):
															A__										=  right_rotation(UpperCAmelCase_			)
										else:
															A__										=  lr_rotation(UpperCAmelCase_			)
					A__										=  my_max(get_height(root.get_right()			)					,   get_height(root.get_left()			)			) + 1
					root.set_height(UpperCAmelCase_			)
					return root



class 					a						:



				"""simple docstring"""



				def __init__(     self: Any       ):






									"""simple docstring"""


									A__										=  None

				def 				UpperCamelCase	(     self: Dict       ):






									"""simple docstring"""


									return get_height(self.root       )

				def 				UpperCamelCase	(     self: Tuple    ,						UpperCamelCase: Any       ):






									"""simple docstring"""


									print("""insert:""" + str(UpperCamelCase       )       )
									A__										=  insert_node(self.root    ,						UpperCamelCase       )

				def 				UpperCamelCase	(     self: str    ,						UpperCamelCase: Any       ):






									"""simple docstring"""


									print("""delete:""" + str(UpperCamelCase       )       )
									if self.root is None:
														print("""Tree is empty!"""       )
														return
									A__										=  del_node(self.root    ,						UpperCamelCase       )





				def __str__(     self: Union[str, Any]    ,						):  # a level traversale, gives a more intuitive look on the tree






									"""simple docstring"""


									A__										=  """"""
									A__										=  MyQueue()
									q.push(self.root       )
									A__										=  self.get_height()
									if layer == 0:
														return output
									A__										=  0
									while not q.is_empty():
														A__										=  q.pop()
														A__										=  """ """ * int(math.pow(2    ,						layer - 1       )       )
														output += space
														if node is None:
																			output += "*"
																			q.push(UpperCamelCase       )
																			q.push(UpperCamelCase       )
														else:
																			output += str(node.get_data()       )
																			q.push(node.get_left()       )
																			q.push(node.get_right()       )
														output += space
														A__										=  cnt + 1
														for i in range(1_00       ):
																			if cnt == math.pow(2    ,						UpperCamelCase       ) - 1:
																								A__										=  layer - 1
																								if layer == 0:
																													output += "\n*************************************"
																													return output
																								output += "\n"
																								break
									output += "\n*************************************"
									return output





def  _snake_case     (    ):
					import doctest

					doctest.testmod()


if __name__ == "__main__":
	_test()
	SCREAMING_SNAKE_CASE_					:	List[str]							  =						AVLtree()
	SCREAMING_SNAKE_CASE_					:	str							  =						list(range(1_0))
	random.shuffle(lst)
	for i in lst:
		t.insert(i)
		print(str(t))
	random.shuffle(lst)
	for i in lst:
		t.del_node(i)
		print(str(t))









"""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)






