# Leetcode 1615. Maximal Network Rank

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        number_of_roads = [0] * n # 紀錄每個城市連接的所有道路數量
        connected = [[False for i in range(n)] for i in range(n)] # 紀錄城市和城市之間是否相連接
        max_roads = 0 # 紀錄兩個城市之間最大道路數量

        for c1,c2 in roads:
            # 紀錄每個城市道路連接的數量
            number_of_roads[c1] += 1
            number_of_roads[c2] += 1

            # 紀錄城市與城市間是否有連接
            connected[c1][c2] = True
            connected[c2][c1] = True

        # 開始走訪所有城市，確認兩個城市加總的道路是否為最大
        for i in range(n):
            for j in range(n):
                # 自己不比
                if i == j:
                    continue
                two_cities_roads = number_of_roads[i] + number_of_roads[j]
                # 如果城市和城市間有道路相連接，則會重複計算到同一條道路，所以需要去掉重複計算的道路
                if connected[i][j] or connected[j][i]:
                    two_cities_roads -= 1
                # 比較是否為最大
                max_roads = max(two_cities_roads,max_roads)
        return max_roads