Problem Description

The Kingdom of Paken consists of $ N $ cities $1,\ 2,\ \ldots,\ N$ and $ M $ roads $1,\ 2,\ \ldots,\ M$, where road $ i $ connects city $ A_i $ and city $ B_i $ bidirectionally.

It is the year 2021, and a new virus has spread throughout the Kingdom of Paken. To curb the movement of people, the roads have been made one-way only. However, to minimize the impact on the economy, we want to maximize the GoTo value, which is defined as follows:

GoTo value: The number of pairs of cities $(u,\ v)$ such that it is possible to travel from city $ u $ to city $ v $ using zero or more roads.

There are $ 2^M $ possible orientations for the roads. Calculate the GoTo value for all of them and output the maximum value.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3 2
1 2
2 3

Sample Output #1

6

Sample Input #2

3 3
1 2
1 3
2 3

Sample Output #2

9

Sample Input #3

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

Sample Output #3

27

Notes/Hints

Constraints

• $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)$
• Assuming each road is bidirectional, it is possible to travel from any city to any other city using zero or more roads.
• All inputs are integers.

Sample Explanation 1

For example, the optimal orientation is $1\ \rightarrow\ 2,\ 2\ \rightarrow\ 3$. In this case, the pairs $ (u,v) $ such that it is possible to travel from $ u $ to $ v $ using zero or more edges are $ (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) $, totaling 6 pairs.

Sample Explanation 2

For example, the optimal orientation is $1\ \rightarrow\ 2,\ 1\ \leftarrow\ 3,\ 2\ \rightarrow\ 3$. In this case, it is possible to travel from any vertex to any other vertex using zero or more edges, so the answer is $3\ \times\ 3\ =\ 9$.

Sample Explanation 3

Original idea: [MATH0]

见题面 Input 部分

见题面 Output 部分