


'''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__  =     {
    '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 				lowerCAmelCase__	(       UpperCAmelCase     ):






       """simple docstring"""





       snake_case__					:	List[Any]          =					{node: {node} for node in graph}

       snake_case__					:	str          =					{node: graph[node][:] for node in graph}

       while len(UpperCAmelCase     ) > 2:
              # Choose a random edge.
              snake_case__					:	List[Any]          =					random.choice(list(graph_copy.keys()     )     )
              snake_case__					:	Dict          =					random.choice(graph_copy[u]     )

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

              snake_case__					:	str          =					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(UpperCAmelCase     )
                     if v in graph_copy[neighbor]:
                            graph_copy[neighbor].remove(UpperCAmelCase     )

    # Find cutset.
       snake_case__					:	Any          =					[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 unittest
from timeit import timeit



def 				lowerCAmelCase__	(       UpperCAmelCase    ,       UpperCAmelCase     ):






       """simple docstring"""





       snake_case__					:	Any          =					first_num if first_num >= second_num else second_num
       snake_case__					:	Optional[Any]          =					max_num
       while (common_mult % first_num > 0) or (common_mult % second_num > 0):
              common_mult += max_num
       return common_mult



def 				lowerCAmelCase__	(       UpperCAmelCase    ,       UpperCAmelCase     ):






       """simple docstring"""





       return b if a == 0 else greatest_common_divisor(b % a    ,       UpperCAmelCase     )



def 				lowerCAmelCase__	(       UpperCAmelCase    ,       UpperCAmelCase     ):






       """simple docstring"""





       return first_num // greatest_common_divisor(UpperCAmelCase    ,       UpperCAmelCase     ) * second_num



def 				lowerCAmelCase__	(       ):






       """simple docstring"""





       snake_case__					:	Tuple          =					(
           """from __main__ import least_common_multiple_slow, least_common_multiple_fast"""
       )
       print(
           """least_common_multiple_slow():"""    ,       timeit("""least_common_multiple_slow(1000, 999)"""    ,       setup=UpperCAmelCase     )    ,       )
       print(
           """least_common_multiple_fast():"""    ,       timeit("""least_common_multiple_fast(1000, 999)"""    ,       setup=UpperCAmelCase     )    ,       )







class 					_A						(						unittest.TestCase							):



   '''simple docstring'''






   _lowercase    						= (
       (10, 20),
       (13, 15),
       (4, 31),
       (10, 42),
       (43, 34),
       (5, 12),
       (12, 25),
       (10, 25),
       (6, 9),
   )
   _lowercase    						= (20, 195, 124, 210, 1462, 60, 300, 50, 18)




   def   __lowerCAmelCase						(	self	:					Optional[int]						)->	Optional[Any]:
          for i, (first_num, second_num) in enumerate(self.test_inputs						):
                 snake_case__					:	List[Any]          =					least_common_multiple_slow(lowerCamelCase					, lowerCamelCase						)
                 snake_case__					:	Optional[Any]          =					least_common_multiple_fast(lowerCamelCase					, lowerCamelCase						)
                 with self.subTest(i=lowerCamelCase						):
                        self.assertEqual(lowerCamelCase					, self.expected_results[i]						)
                        self.assertEqual(lowerCamelCase					, self.expected_results[i]						)


if __name__ == "__main__":
     benchmark()
     unittest.main()




