G - ギガ国の道路事情 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 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