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

可复制的 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