実行時間制限: 3 sec / メモリ制限: 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 つしか存在しない.
- どの都市からどの都市へも,道路を辿って行くことができる.
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (9 点) N \leq 100, M \leq 100
- (7 点) N \leq 3 \ 000, M \leq 3 \ 000
- (12 点) M - N = -1 を満たす.
- (13 点) M - N = 0 を満たす.
- (28 点) M - N \leq 7 を満たす.また,1 \leq i \leq N-1 について,a_i = i, b_i = i+1 を満たす.
- (22 点) M - N \leq 77 を満たす.
- (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