問題文

Paken 王国は N 個の街 1, 2, \ldots, N と M 本の道路 1, 2, \ldots, M からなり、道路 i は街 A_i と街 B_i を双方向に結んでいます。

時は 2021 年、 Paken 王国にも新型ウイルスが蔓延したため、道路に向きを付けて片方向にしか通れないようにし、人の移動を抑えることになりました。 しかし、経済への影響は小さくしたいので、次のように定義されるGoTo度をできるだけ大きくしたいです。

GoTo度 : 街 u から街 v に 0 本以上の道路を通って移動できるような街の組 (u, v) の個数

道路の向き付けとして考えられるものは 2^M 通りありますが、その全てについてGoTo度を求め、その中の最大値を出力してください。

制約

• 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

3 2
1 2
2 3

出力例 1

6

例えば、 1 \rightarrow 2, 2 \rightarrow 3 という向きにするのが最適です。

この時、 u から v へと 0 本以上の辺を通り移動できるような (u,v) の組は、 (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) の 6 つです。

入力例 2

3 3
1 2
1 3
2 3

出力例 2

9

例えば、 1 \rightarrow 2, 1 \leftarrow 3, 2 \rightarrow 3 という向きにするのが最適です。

この時、任意の頂点から任意の頂点に 0 本以上の辺を通り移動できるため、答えは 3 \times 3 = 9 です。

入力例 3

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

出力例 3

27

原案: shiomusubi496