← 返回题目列表

Codeforces · 1089/D

D. 距离总和

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

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Distance Sum - 原题 PDF 第 1 页
原题PDF第5页
可复制的 PDF 提取文本
ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018
Problem D. Distance Sum

You are given a connected undirected unweighted graph. The distance d(u, v) between two vertices u and
v is de ned as the number of edges in the shortest path between them. Find the sum of d(u, v) over all
unordered pairs (u, v).

Input

The  rst line of the input contains two integers n and m (2 ≤n ≤105; n−1 ≤m ≤n+42)   the number
of vertices and the number of edges in the graph respectively. The vertices are numbered from 1 to n.

Each of the following m lines contains two integers xi and yi (1 ≤xi, yi ≤n; xi ̸= yi)   the endpoints of
the i-th edge.

There is at most one edge between every pair of vertices.

Output

Output a single integer   the sum of the distances between all unordered pairs of vertices in the graph.

Examples

   standard input     standard output                   Illustration
 4 4                 8
 1 2
                                                      1 2 3
 3 1                                                              3            4
 3 4
                                                      2


 7 10                34
 1 2
                                               7            5            3 2 6
 5 3                                                                                  6
 5 4
                                               4            1            2 5 7
 3 6
 1 7
 5 1
 7 4
 4 1

Note

In the  rst example the distance between four pairs of vertices connected by an edge is equal to 1 and
d(1, 4) = d(2, 4) = 2.





                                         Page 5 of 15