P8905 [USACO22DEC] Strongest Friendship Group G

Farmer John has $N$ cows ($2 \le N \le 10^5$), numbered $1 \cdots N$. Among these cows, there are $M$ ($1 \le M \le 2 \times 10^5$) pairs of friends. A group of cows is called a "friend group" if, for every cow in the group, it can reach every other cow in the group by following a sequence of friendships that stays entirely within the group (friendships that connect to cows outside the group are invalid). The "strength" of a friend group is defined as: (the minimum number of in-group friends among cows in the group) $\times$ (the number of cows in the group) (again, note that friendships connecting to cows outside the group are not counted in this definition). Find the maximum strength among all friend groups.

The first line contains $N$ and $M$. The next $M$ lines each contain two integers $u_i$ and $v_i$, indicating that cows $u_i$ and $v_i$ are friends ($1 \le u_i, v_i \le N$, $u_i \neq v_i$). Each unordered pair of cows appears at most once.

Output one line containing the maximum strength among all friend groups.

### Explanation for Sample 1 It can be seen that the maximum strength comes from the group of cows numbered $1, 2, 3, 4$. In this group, the minimum number of friends is $3$, so the answer is $4 \times 3 = 12$. ### Test Point Properties - For $1 \le T \le 3$, test point $T$ satisfies $N \le 16$. - For $4 \le T \le 9$, test point $T$ satisfies $N \le 1000$. - For $10 \le T \le 20$, test point $T$ has no additional constraints. Translated by ChatGPT 5