You are given an integer n denoting the number of cities labeled from $0$ to n $- 1$. You are also given a $2$D integer array roads where roads[i] $= [a_i, b_i]$ indicates a bidirectional road connecting cities $a_i$ and $b_i$.

Assign each city an integer value from $1$ to n such that each value is used exactly once. The importance of a road is defined as the sum of the values assigned to the two cities it connects.

Return the maximum possible total importance of all roads after assigning the values optimally.

Constraints:

• $2 \leq$ n $\leq 5 imes 10^4$

• $1 \leq$ roads.length $\leq 5 imes 10^4$

• roads[i].length $= 2$

• $0 \leq a_i, b_i \leq$ n $- 1$

• $a_i \neq b_i$

• There are no duplicate roads.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.