n cities are connected by m bidirectional roads. For any two cities directly connected by a road, their network rank is the number of roads incident to either city, counting the shared road once. Return the maximum network rank across all directly connected pairs.
Input
starts: array of length m, starts[i] is one endpoint of road i
ends: array of length m, ends[i] is the other endpoint of road i
n: number of cities
Output
The maximum network rank.
Examples
Example 1
Inputstarts = [1, 2, 3, 3], ends = [2, 3, 1, 4], n = 4
Output4
Explanation: Pair (2, 3) touches roads (1,2), (2,3), (1,3), (3,4). Degree(2)=2, degree(3)=3, minus 1 shared road = 4.
Example 2
Inputstarts = [10, 20], ends = 0, n = 2
Output2
Constraints
Compute degree of each city, then for each road return max(deg[u] + deg[v] - 1).