Assign node labels to maximize the total edge sum

You are given an undirected graph with n nodes numbered 0 to n - 1 and a list edges, where edges[i] = [a, b] is an edge between nodes a and b.

Give every node a label so that the labels are exactly the integers 1 to n, each used once. The value of an edge (u, v) is label(u) + label(v).

Implement max_edge_sum(n: int, edges: list[list[int]]) -> int that returns the largest possible total value over all edges, taken over every valid labeling.

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= len(edges) <= 5 * 10^4
• 0 <= a, b < n, a != b; no duplicate edges
• Some nodes may have no edges.

Example 1

n = 4, edges = [[0,1],[0,2],[0,3]]
Output: 18

Node 0 touches all three edges, so it gets label 4; nodes 1, 2, 3 get labels 1, 2, 3. Total = (4+1) + (4+2) + (4+3) = 18.

Example 2

n = 5, edges = [[3,4]]
Output: 9

Only one edge exists, so its endpoints take the two largest labels, 4 and 5.