配点: $100$ 点

問題文

ギガ国には $N$ 個の都市があり，それぞれ $1, 2, 3, \\dots, N$ と番号が付けられています．

いくつかの都市は道路でつながれています．具体的には，$M$ 本の道路があり，$i$ 本目の道路は都市 $a_i$ と $b_i$ を双方向に結んでいます．また，いくつかの道路だけを通ることによって，どの都市からどの都市へも行けるようになっています．

ここで，$d(i, j)$ を，「都市 $i$ と $j$ の距離」，つまり「都市 $i$ から都市 $j$ に道路だけを使って行くときに使う，最小の道路の本数」とします．

そのとき，すべての異なる $2$ 都市の組 $(x, y)$ に対しての距離 $d(x, y)$ の合計を求めて下さい．

制約

• $1 \\leq N \\leq 100 \\ 000$
• $1 \\leq M \\leq 100 \\ 000$
• $N - 1 \\leq M \\leq N + 777$
• $1 \\leq a_i, b_i \\leq N$
• $a_i \\neq b_i$
• どのような $(u, v)$ の組においても，都市 $u$ と都市 $v$ を直接結ぶ道路は高々 1 つしか存在しない．
• どの都市からどの都市へも，道路を辿って行くことができる．
• 入力はすべて整数

---

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (9 点) $N \\leq 100, M \\leq 100$
2. (7 点) $N \\leq 3 \\ 000, M \\leq 3 \\ 000$
3. (12 点) $M - N = -1$ を満たす．
4. (13 点) $M - N = 0$ を満たす．
5. (28 点) $M - N \\leq 7$ を満たす．また，$1 \\leq i \\leq N-1$ について，$a_i = i, b_i = i+1$ を満たす．
6. (22 点) $M - N \\leq 77$ を満たす．
7. (9 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ : : $a_M$ $b_M$

---

出力

全ての都市 $x, y$ 間の距離 $d(x, y)$ の合計を出力してください．

注意

この問題は入出力のサイズがやや大きいため，高速な入出力（C++ の場合 scanf/printf など）を用いることが推奨されます．

---

入力例 1

4 3
1 2
2 3
3 4

出力例 1

10

ギガ国は，以下のような道路網を持ちます．

この道路網において，$d(1, 2) = 1, d(1, 3) = 2, d(1, 4) = 3, d(2, 3) = 1, d(2, 4) = 2, d(3, 4) = 1$ より，答えは $1+2+3+1+2+1=10$ となります．

---

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

6

ギガ国は，以下のような道路網を持ちます．

この道路網において，すべての都市間を距離 $1$ で移動できるので，答えは $6$ となります．

---

入力例 3

9 12
1 2
2 3
4 5
5 6
7 8
8 9
1 4
4 7
2 5
5 8
3 6
6 9

出力例 3

72