


'''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
lowercase__					  =		{
    '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		:			int					)   ->  Tuple:







     '''simple docstring'''






     _a            =		{node: {node} for node in graph}

     _a            =		{node: graph[node][:] for node in graph}

     while len(lowerCAmelCase_					) > 2:
          # Choose a random edge.
          _a            =		random.choice(list(graph_copy.keys()					)					)
          _a            =		random.choice(graph_copy[u]					)

          # Contract edge (u, v) to new node uv
          _a            =		u + v
          _a            =		list(set(graph_copy[u] + graph_copy[v]					)					)
          uv_neighbors.remove(lowerCAmelCase_					)
          uv_neighbors.remove(lowerCAmelCase_					)
          _a            =		uv_neighbors
          for neighbor in uv_neighbors:
               graph_copy[neighbor].append(lowerCAmelCase_					)

          _a            =		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.
     _a            =		[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  _a     (				lowerCAmelCase_						):





      """simple docstring"""



      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  _a     (				lowerCAmelCase_ = 2_000_000						):





      """simple docstring"""



      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() = }""")


