class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] times = new int[n];
        for (int[] r: roads) {
            times[r[0]]++;
            times[r[1]]++;
        }

        int[] time = new int[roads.length + 1];
        for (int t: times) {
            time[t]++;
        }

        int pointer = n;
        long result = 0;
        boolean flag = true;
        for (int i=roads.length; i>=0; i--) {
            if (time[i] > 0) {
                result += (2 * pointer - time[i] + 1) * (long) time[i] * (long) i / 2;
                pointer -= time[i];
            }
        }

        return result;
    }
}