


"""simple docstring"""






def __lowercase     (      lowerCamelCase_  :      List[str]  ):
				return [
				    {
				        0: [1, 2],
				        1: [0, 2],
				        2: [0, 1, 3, 5],
				        3: [2, 4],
				        4: [3],
				        5: [2, 6, 8],
				        6: [5, 7],
				        7: [6, 8],
				        8: [5, 7],
				    },
				    {
				        0: [6],
				        1: [9],
				        2: [4, 5],
				        3: [4],
				        4: [2, 3],
				        5: [2],
				        6: [0, 7],
				        7: [6],
				        8: [],
				        9: [1],
				    },
				    {
				        0: [4],
				        1: [6],
				        2: [],
				        3: [5, 6, 7],
				        4: [0, 6],
				        5: [3, 8, 9],
				        6: [1, 3, 4, 7],
				        7: [3, 6, 8, 9],
				        8: [5, 7],
				        9: [5, 7],
				    },
				    {
				        0: [1, 3],
				        1: [0, 2, 4],
				        2: [1, 3, 4],
				        3: [0, 2, 4],
				        4: [1, 2, 3],
				    },
				][index]


def __lowercase     (      lowerCamelCase_  :      Any  ):
				SCREAMING_SNAKE_CASE__     							=				0
				SCREAMING_SNAKE_CASE__     							=				len(__SCREAMING_SNAKE_CASE  )  # No of vertices in graph
				SCREAMING_SNAKE_CASE__     							=				[0] * n
				SCREAMING_SNAKE_CASE__     							=				[False] * n

				def dfs(lowerCamelCase_  :      Optional[int]						,					lowerCamelCase_  :      str						,					lowerCamelCase_  :      str						,					lowerCamelCase_  :      Tuple  ):
								SCREAMING_SNAKE_CASE__     							=				True
								SCREAMING_SNAKE_CASE__     							=				id_
								id_ += 1
								for to in graph[at]:
												if to == parent:
																pass
												elif not visited[to]:
																dfs(__SCREAMING_SNAKE_CASE						,					__SCREAMING_SNAKE_CASE						,					__SCREAMING_SNAKE_CASE						,					id_  )
																SCREAMING_SNAKE_CASE__     							=				min(low[at]						,					low[to]  )
																if id_ <= low[to]:
																				bridges.append((at, to) if at < to else (to, at)  )
												else:
																# This edge is a back edge and cannot be a bridge
																SCREAMING_SNAKE_CASE__     							=				min(low[at]						,					low[to]  )

				SCREAMING_SNAKE_CASE__     							=				[]
				for i in range(__SCREAMING_SNAKE_CASE  ):
								if not visited[i]:
												dfs(__SCREAMING_SNAKE_CASE						,					-1						,					__SCREAMING_SNAKE_CASE						,					id_  )
				return bridges


if __name__ == "__main__":
	import doctest

	doctest.testmod()




"""simple docstring"""






import heapq


def __lowercase     (      lowerCamelCase_  :      dict  ):
				SCREAMING_SNAKE_CASE__     							=				[]

				# for each node and his adjacency list add them and the rank of the node to queue
				# using heapq module the queue will be filled like a Priority Queue
				# heapq works with a min priority queue, so I used -1*len(v) to build it
				for key, value in graph.items():
								# O(log(n))
								heapq.heappush(lowerCamelCase_						,					[-1 * len(lowerCamelCase_  ), (key, value)]  )

				# chosen_vertices = set of chosen vertices
				SCREAMING_SNAKE_CASE__     							=				set()

				# while queue isn't empty and there are still edges
				#   (queue[0][0] is the rank of the node with max rank)
				while queue and queue[0][0] != 0:
								# extract vertex with max rank from queue and add it to chosen_vertices
								SCREAMING_SNAKE_CASE__     							=				heapq.heappop(lowerCamelCase_  )[1][0]
								chosen_vertices.add(lowerCamelCase_  )

								# Remove all arcs adjacent to argmax
								for elem in queue:
												# if v haven't adjacent node, skip
												if elem[0] == 0:
																continue
												# if argmax is reachable from elem
												# remove argmax from elem's adjacent list and update his rank
												if argmax in elem[1][1]:
																SCREAMING_SNAKE_CASE__     							=				elem[1][1].index(lowerCamelCase_  )
																del elem[1][1][index]
																elem[0] += 1
        # re-order the queue
								heapq.heapify(lowerCamelCase_  )
				return chosen_vertices


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	_lowerCamelCase     =  {0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]}
	print(f"""Minimum vertex cover:\n{greedy_min_vertex_cover(graph)}""")
