CF475E.Strongly Connected City 2

Imagine a city with n junctions and m streets. Junctions are numbered from 1 to n.

In order to increase the traffic flow, mayor of the city has decided to make each street one-way. This means in the street between junctions u and v, the traffic moves only from u to v or only from v to u.

The problem is to direct the traffic flow of streets in a way that maximizes the number of pairs (u, v) where 1 ≤ u, v ≤ n and it is possible to reach junction v from u by passing the streets in their specified direction. Your task is to find out maximal possible number of such pairs.

设想一座拥有 $n$ 个路口和 $m$ 条街道的城市。路口编号为 $1$ 到 $n$。

为了提升交通流量，该城市的市长决定将每条街道改为单向通行。这意味着：对于连接路口 $u$ 和 $v$ 的街道，交通流仅允许从 $u$ 到 $v$，或仅允许从 $v$ 到 $u$。

问题在于：如何为所有街道指定方向，使得满足如下条件的有序对 $(u,\,v)$ 的数量最大化——其中 $1 \le u,\,v \le n$，且存在一条从路口 $u$ 到路口 $v$ 的有向路径（即沿街道指定方向连续通行）。你的任务是求出此类有序对的最大可能数量。

The first line of input contains integers n and m, (), denoting the number of junctions and streets of the city.

Each of the following m lines contains two integers u and v, (u ≠ v), denoting endpoints of a street in the city.

Between every two junctions there will be at most one street. It is guaranteed that before mayor decision (when all streets were two-way) it was possible to reach each junction from any other junction.

输入的第一行包含两个整数 $n$ 和 $m$（），分别表示城市的路口数量和街道数量。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$u \ne v$），表示城市中某条街道的两个端点。

任意两个路口之间至多存在一条街道。保证在市长做出决策之前（即所有街道均为双向通行时），从任一路口均可到达其他任意路口。

Print the maximal number of pairs (u, v) such that that it is possible to reach junction v from u after directing the streets.

输出在对街道进行定向后，能够从结点 $u$ 到达结点 $v$ 的结点对 $(u,\,v)$ 的最大可能数量。

In the first sample, if the mayor makes first and second streets one-way towards the junction 1 and third and fourth streets in opposite direction, there would be 13 pairs of reachable junctions: {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}

在第一个样例中，如果市长将第一条和第二条街道设为指向路口 1 的单向道路，将第三条和第四条街道设为相反方向的单向道路，则将有 13 对可达的路口：{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}