Assign the distinct values 1 through n to the n cities labeled 0 through n - 1, using each value exactly once. Each pair [u, v] in roads represents a bidirectional road between those cities.
A road's importance is the sum of the values assigned to its two endpoints. Return the largest possible sum of importance over all roads. Return the total, not the assignment.
Cities with no roads still receive values. Roads are distinct and never connect a city to itself.
Example 1:
Input: n = 4
roads = [[0,1],[0,2],[0,3]]
Output: 18Explanation: Give city 0 value 4 because it belongs to all three roads. The other cities receive 1, 2, and 3 in any order, giving a total of 3 × 4 + 1 + 2 + 3 = 18.
Example 2:
Input: n = 5
roads = [[1,3]]
Output: 9Explanation: Assign values 5 and 4 to cities 1 and 3, the only cities on a road. Their road has importance 9. Values 1, 2, and 3 go to the isolated cities.
Example 3:
Input: n = 4
roads = [[0,1],[1,2],[2,3],[3,0]]
Output: 20Explanation: Every city belongs to exactly two roads. Each assigned value therefore contributes twice, giving 2 × (1 + 2 + 3 + 4) = 20 for any assignment.
Constraints:
2 <= n <= 500001 <= roads.length <= 50000roads[i].length == 2- Road endpoints are distinct city labels between
0andn - 1. - No bidirectional road appears more than once.