← 返回题目列表

AtCoder · nadafes2022_day2_h

H. 图上的游客

中文机器翻译题面 查看原题

配点 : 600 点

問題文

N 頂点 M 给出了一个简单连接的无向边图。i \, (1 \leq i \leq M) 真正的边是顶点 连接 A_i, B_i 。 满足

1 \leq s \lt t \leq N 的整数集合 对于 (s, t) ,输入以下值: f(s, t) 。 从

頂点 s 开始,顶点 到达 t 后的顶点 在返回 s 的路线中, 在除s 之外的顶点中 2 多次通过的最小项目数

\displaystyle \sum_{s = 1}^{N - 1} \sum_{t = s + 1}^N f(s, t) 。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) \, (1 \leq i \lt j \leq M)
  • 给定的图形已连接
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
\vdots
A_M B_M

出力

输出答案。


入力例 1

4 4
1 2
2 3
1 3
3 4

出力例 1

2

例如 维度平面上的 f(1, 4) = 1, f(3, 4) = 0 。


入力例 2

2 1
1 2

出力例 2

0