"""simple docstring"""


from collections import defaultdict






def     __UpperCAmelCase					(			lowercase		):







  """simple docstring"""
  _UpperCAmelCase						 =      1
  _UpperCAmelCase						 =      True
  for v in tree[start]:
    if v not in visited:
      ret += dfs(lowercase		)
  if ret % 2 == 0:
    cuts.append(lowercase		)
  return ret






def     __UpperCAmelCase					(			):







  """simple docstring"""
  dfs(1		)


if __name__ == "__main__":
    UpperCAmelCase__		,   UpperCAmelCase__  		=						1_0, 9
    UpperCAmelCase__  		=						defaultdict(list)
    UpperCAmelCase__  		=						{}
    UpperCAmelCase__  		=						[]
    UpperCAmelCase__  		=						0
    UpperCAmelCase__  		=						[(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)

"""simple docstring"""


import random






def     __UpperCAmelCase					(			lowercase   ,lowercase   ,lowercase = False		):







  """simple docstring"""
  _UpperCAmelCase						 =      {i: [] for i in range(lowercase		)}

  # if probability is greater or equal than 1, then generate a complete graph
  if probability >= 1:
    return complete_graph(lowercase		)
  # if probability is lower or equal than 0, then return a graph without edges
  if probability <= 0:
    return graph

  # for each couple of nodes, add an edge from u to v
  # if the number randomly generated is greater than probability probability
  for i in range(lowercase		):
    for j in range(i + 1   ,lowercase		):
      if random.random() < probability:
        graph[i].append(lowercase		)
        if not directed:
          # if the graph is undirected, add an edge in from j to i, either
          graph[j].append(lowercase		)
  return graph






def     __UpperCAmelCase					(			lowercase		):







  """simple docstring"""
  return {
      i: [j for j in range(lowercase		) if i != j] for i in range(lowercase		)
  }


if __name__ == "__main__":
    import doctest

    doctest.testmod()
