AT_tkppc6_2_l.Go To

Paken 王国由 $N$ 个城市 $1, 2, \ldots, N$ 和 $M$ 条道路 $1, 2, \ldots, M$ 组成，道路 $i$ 连接城市 $A_i$ 和城市 $B_i$，且道路是双向的。

时间来到 2021 年，由于新型病毒在 Paken 王国蔓延，为了抑制人员流动，决定给每条道路指定一个方向，使其只能单向通行。然而，为了尽量减少对经济的影响，希望使下述定义的 GoTo 度 尽可能大。

GoTo 度：能够从城市 $u$ 经过 $0$ 条或多条道路到达城市 $v$ 的城市对 $(u, v)$ 的数量。

对于道路的方向指定，共有 $2^M$ 种可能。请你计算所有可能的方向指定方式中，GoTo 度的最大值，并输出该最大值。

输入以如下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

请输出一行答案。

限制条件

• $1 \leq N, M \leq 10^5$
• $1 \leq A_i < B_i \leq N$ $(1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j)$ $(1 \leq i < j \leq M)$
• 如果所有道路都为双向，则任意城市之间都可以通过 $0$ 条或多条道路互相到达
• 输入均为整数

样例解释 1

例如，将道路方向设为 $1 \rightarrow 2, 2 \rightarrow 3$ 是最优的。在这种情况下，能够从 $u$ 经过 $0$ 条或多条道路到达 $v$ 的 $(u, v)$ 共有 $6$ 组，分别为 $(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)$。

样例解释 2

例如，将道路方向设为 $1 \rightarrow 2, 1 \leftarrow 3, 2 \rightarrow 3$ 是最优的。在这种情况下，任意顶点都可以到达任意顶点，因此答案为 $3 \times 3 = 9$。

样例解释 3

原案: shiomusubi496

由 ChatGPT 4.1 翻译