Untitled

class Solution {
public:
    int cut(vector<vector<int>>& roads, vector<int> counts, int maxCity)
    {
        int maxRank = 0;
        for (const auto& road : roads)
        {
            if (road[0] == maxCity)
            {
                --counts[road[1]];
            }
            if (road[1] == maxCity)
            {
                --counts[road[0]];
            }
        }
        for (int i = 0; i < counts.size(); ++i)
        {
            if (i != maxCity && counts[i] > maxRank)
            {
                maxRank = counts[i];
            }
        }

        return maxRank;
    }

    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> counts(n, 0);
        for (const auto& road : roads)
        {
            ++counts[road[0]];
            ++counts[road[1]];
        }

        int maxCity1 = distance(counts.begin(), max_element(counts.begin(), counts.end()));
        int maxCity2;
        for (int i = counts.size() - 1; i >= 0; --i)
        {
            if (counts[i] == counts[maxCity1])
            {
                maxCity2 = i;
                break;
            }
        }
    
        if (maxCity1 != maxCity2)
        {
            return max(cut(roads, counts, maxCity1), cut(roads, counts, maxCity2)) + counts[maxCity1];
        }
        else
        {
            return cut(roads, counts, maxCity1) + counts[maxCity1];
        }
    }
};