

'''simple docstring'''







import heapq
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     set[int]:
       A_		   = []

       # 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(UpperCAmelCase__,    [-1 * len(UpperCAmelCase__			), (key, value)]			)

       # chosen_vertices = set of chosen vertices
       A_		   = 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
              A_		   = heapq.heappop(UpperCAmelCase__			)[1][0]
              chosen_vertices.add(UpperCAmelCase__			)

              # 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]:
                            A_		   = elem[1][1].index(UpperCAmelCase__			)
                            del elem[1][1][index]
                            elem[0] += 1
        # re-order the queue
              heapq.heapify(UpperCAmelCase__			)
       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)}""")



'''simple docstring'''







def  UpperCAmelCase__      ( UpperCAmelCase__ = 10_00			)     ->     int:
       return sum(2 * a * ((a - 1) // 2) for a in range(3,    n + 1			)			)


if __name__ == "__main__":
      print(solution())
