You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.

You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

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

&nbsp;
Example 1:

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.


Example 2:

Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20
Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 5 * 104
	1 &lt;= roads.length &lt;= 5 * 104
	roads[i].length == 2
	0 &lt;= ai, bi &lt;= n - 1
	ai != bi
	There are no duplicate roads.


class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        Arr = [0] * n  # i-th city has Arr[i] roads
        for A,B in roads:
            Arr[A] += 1 # Each road increase the road count
            Arr[B] += 1
        Arr.sort()  # Cities with most road should receive the most score
        summ = 0
        for i in range(len(Arr)):
            summ += Arr[i] * (i+1)  # Multiply city roads with corresponding score
        
        return summ
class Solution {
    public long maximumImportance(int n, int[][] roads) {
        long ans = 0, x = 1;
        long degree[] = new long[n];
        for(int road[] : roads){
            degree[road[0]]++;
            degree[road[1]]++;
        }
        Arrays.sort(degree);
        for(long i : degree) ans += i * (x++) ;
        return ans;
    }
}
class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int>ind(n,0);
        
        for(auto it:roads)
        {
            ind[it[0]]++;
            ind[it[1]]++;
        }
        
        priority_queue<long long> pq;
        long long val = n,ans=0;
        
        for(int i=0;i<n;i++)
            pq.push(ind[i]);
        
        while(!pq.empty())
        {
            ans += pq.top() * val;
            val--;
            pq.pop();
        }
        return ans;
    }
};
var maximumImportance = function(n, roads) {
    const connectionCount = Array(n).fill(0)

    // Count the connections from each city
    // e.g. the 0th city's count will be stored at index zero in the array
    for (let [cityTo, cityFrom] of roads) {
        connectionCount[cityTo]++
        connectionCount[cityFrom]++
    }

    let cityToConnectionCount = []
    for (let city = 0; city < n; city++) {
        cityToConnectionCount.push([city, connectionCount[city]])// Store the [city, numberOfConnections]
    }

    // Created new array(sortedCities) for readability
    const sortedCities = cityToConnectionCount.sort((a,b) => b[1] - a[1])// sort by number of connections, the city with the greatest number of connections should be
    // the city with the greatest importance

    const values = Array(n).fill(0)
    let importance = n
    for (let i = 0; i < sortedCities.length; i++) {
        const [city, connectionCount] = cityToConnectionCount[i]
        values[city] = importance// City at the 0th position array is should be the city with the greatest importance
        importance--
    }

    // Sum the importance of each city, toCity => fromCity
    let res = 0
    for (let [to, from] of roads) {
        res += values[to] + values[from]
    }

    return res
};```
Maximum Total Importance of Roads