





'''simple docstring'''


from __future__ import annotations

import random

# Adjacency list representation of this graph:
# https://en.wikipedia.org/wiki/File:Single_run_of_Karger%E2%80%99s_Mincut_algorithm.svg
lowerCAmelCase      :  Optional[int]      							={
    '''1''': ['''2''', '''3''', '''4''', '''5'''],
    '''2''': ['''1''', '''3''', '''4''', '''5'''],
    '''3''': ['''1''', '''2''', '''4''', '''5''', '''10'''],
    '''4''': ['''1''', '''2''', '''3''', '''5''', '''6'''],
    '''5''': ['''1''', '''2''', '''3''', '''4''', '''7'''],
    '''6''': ['''7''', '''8''', '''9''', '''10''', '''4'''],
    '''7''': ['''6''', '''8''', '''9''', '''10''', '''5'''],
    '''8''': ['''6''', '''7''', '''9''', '''10'''],
    '''9''': ['''6''', '''7''', '''8''', '''10'''],
    '''10''': ['''6''', '''7''', '''8''', '''9''', '''3'''],
}
def 							UpperCAmelCase_						(		__lowerCamelCase      :      dict[str, list[str]]				):
   lowercase_    :Union[str, Any]					    =				{node: {node} for node in graph}

   lowercase_    :Optional[int]					    =				{node: graph[node][:] for node in graph}

   while len(__lowerCamelCase				) > 2:
      # Choose a random edge.
      lowercase_    :int					    =				random.choice(list(graph_copy.keys()				)				)
      lowercase_    :List[str]					    =				random.choice(graph_copy[u]				)

      # Contract edge (u, v) to new node uv
      lowercase_    :Optional[int]					    =				u + v
      lowercase_    :List[Any]					    =				list(set(graph_copy[u] + graph_copy[v]				)				)
      uv_neighbors.remove(__lowerCamelCase				)
      uv_neighbors.remove(__lowerCamelCase				)
      lowercase_    :Any					    =				uv_neighbors
      for neighbor in uv_neighbors:
         graph_copy[neighbor].append(__lowerCamelCase				)

      lowercase_    :Optional[int]					    =				set(contracted_nodes[u].union(contracted_nodes[v]				)				)

      # Remove nodes u and v.
      del graph_copy[u]
      del graph_copy[v]
      for neighbor in uv_neighbors:
         if u in graph_copy[neighbor]:
            graph_copy[neighbor].remove(__lowerCamelCase				)
         if v in graph_copy[neighbor]:
            graph_copy[neighbor].remove(__lowerCamelCase				)

    # Find cutset.
   lowercase_    :List[str]					    =				[contracted_nodes[node] for node in graph_copy]
   return {
       (node, neighbor)
       for node in groups[0]
       for neighbor in graph[node]
       if neighbor in groups[1]
   }


if __name__ == "__main__":
 print(partition_graph(TEST_GRAPH))









'''simple docstring'''


import math
def 							UpperCAmelCase_						(		__lowerCamelCase      :      int				):

   if 1 < number < 4:
      # 2 and 3 are primes
      return True
   elif number < 2 or number % 2 == 0 or number % 3 == 0:
      # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
      return False

   # All primes number are in format of 6k +/- 1
   for i in range(5			,int(math.sqrt(__lowerCamelCase				) + 1				)			,6				):
      if number % i == 0 or number % (i + 2) == 0:
         return False
   return True
def 							UpperCAmelCase_						(		__lowerCamelCase      :      int = 2_00_00_00				):
   return sum(num for num in range(3			,__lowerCamelCase			,2				) if is_prime(__lowerCamelCase				)				) + 2 if n > 2 else 0


if __name__ == "__main__":
 print(F'''{solution() = }''')


