[USACO22DEC] Strongest Friendship Group G

题目描述

Farmer John 有 $N$ 头奶牛($2 \le N \le 10^5$),编号为 $1\cdots N$。这些奶牛中有 $M(1 \le M \le 2\times 10^5)$ 对朋友。 一组奶牛被称为是「小团体」,如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达(连接到组外奶牛的朋友关系无效)。小团体的「强度」是组内奶牛的最小组内朋友数乘以组内奶牛的数量(同样,注意连接到组外奶牛的朋友关系不计入此定义)。 求所有小团体的最大强度。

输入输出格式

输入格式


输入的第一行包含 $N$ 和 $M$。 以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$,表示奶牛 $u_i$ 和 $v_i$ 是朋友($1 \le u_i,v_i \le N,u_i\neq v_i$)。每个奶牛无序对至多出现一次。

输出格式


输出一行,包含所有小团体的最大强度。

输入输出样例

输入样例 #1

8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 8

输出样例 #1

12

说明

### 样例 1 解释 可以观察到最大强度来自编号为 $1,2,3,4$ 的奶牛组。该组内奶牛的最小朋友数为 $3$,故答案为 $4 \times 3=12$。 ### 测试点性质 - 对于 $1 \le T \le 3$,测试点 $T$ 满足 $N \le 16$。 - 对于 $4 \le T \le 9$,测试点 $T$ 满足 $N \le 1000$。 - 对于 $10 \le T \le 20$,测试点 $T$ 没有额外限制。