AT_gigacode_2019_g ギガ国の道路事情

[problemUrl]: https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_g ギガ国には $ 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) $ の合計を求めて下さい．

入力は以下の形式で標準入力から与えられます． > $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : : $ a_M $ $ b_M $

全ての都市 $ 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 点) 追加の制約はない． ### 注意 **この問題は入出力のサイズがやや大きいため，高速な入出力（C++ の場合 scanf/printf など）を用いることが推奨されます．** ### Sample Explanation 1 ギガ国は，以下のような道路網を持ちます． !\[ \](https://img.atcoder.jp/gigacode-2019/da8b47de5e5b0d572877df4fad32b765.png) この道路網において，$ 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 $ となります． ### Sample Explanation 2 ギガ国は，以下のような道路網を持ちます． !\[ \](https://img.atcoder.jp/gigacode-2019/9d66f038cfea1b8b909ce8b378c360e6.png) この道路網において，すべての都市間を距離 $ 1 $ で移動できるので，答えは $ 6 $ となります．