\(N\) 頂点 \(M\) 辺の単純連結な無向グラフ \(G\) が与えられます。 \(i\) \((1 \leq i \leq M)\) 番目の辺は頂点 \(u_i\) と頂点 \(v_i\) を双方向に結びます。
グラフ中の各辺に適切な向きをつけたときの、到達可能な頂点対の数の最大値を求めてください。
※ 到達可能な頂点対の数とは、 \(f(s, t)\) を頂点 \(s\) から頂点 \(t\) へ到達可能ならば \(1\) 、そうでなければ \(0\) であるような関数としたときに、以下で表される値となります。 \[\sum_{1\leq s,t\leq N}f(s,t)\]
入力は以下の形式で標準入力から与えられます。
| \(N~M\) | |
| \(u_1~v_1\) | |
| \(u_2~v_2\) | |
| \(\vdots\) | |
| \(u_M~v_M\) |
入力は以下の制約をすべて満たします。
最大値を出力してください
4 31 21 31 4
9
8 111 22 31 31 41 54 52 65 65 72 73 8
57
例\(1\)：辺\(1\)：頂点\(1\) \(\rightarrow\) 頂点\(2\)，辺\(2\)：頂点\(1\) \(\rightarrow\) 頂点\(3\)，辺\(3\)：頂点\(4\) \(\rightarrow\) 頂点\(1\) に向けることで最大値を達成することができます．