Problem Statement

Maximize friendship power There are N cities and M bi-directional roads connecting some/all of them. 2 cities are connected if they are reachable from each other using the roads. Connected cities form a kingdom. Therefore, you can have at least 1 kingdom (if all are connected) or N kingdoms (M = 0). There are N groups of people. The i th group has A i people. Choose a permutation array B of [1..N] and assign the i th group to the B[i] th city. All people living in a kingdom are friends. The friendship power of a kingdom is defined as the number of different friendship pairs in the kingdom. Choose a permutation array B to maximize the sum of friendship power over all the kingdoms. The maximum friendship value can be very large. Therefore, return the value modulo 998244353. Notes Assume 1-based indexing. Do not count the same friendship pairs twice. That is, if x and y are friends, count this pair only once. 2 cities are connected if they are reachable from each other using the roads. Th