题意
给定一个 N 个顶点 M 条边的无向连通图，记 d(i,j) 表示顶点 i 到顶点 j 的最短路径，试求出 ∑i=1n∑j=ind(i,j)。
1≤N,M≤105
N−1≤M≤N+777
保证没有自环或重边。
部分分
1. N,M≤100（9 分）
2. N,M≤3000（7 分）
3. 保证该图是一棵树 （12 分）
4. N=M （13 分）
5. M−N≤7，且保证图中存在一条顺次连接 1,2,…,N 的链 （28 分）
6. M−N≤77 （22 分）
7. 无特殊条件 （9 分）
### 题意
给定一个 $N$ 个顶点 $M$ 条边的无向连通图，记 $d(i,j)$ 表示顶点 $i$ 到顶点 $j$ 的最短路径，试求出 $\sum_{i=1}^{n}\sum_{j=i}^{n}d(i,j)$。
$1\leq N,M\leq 10^5$
$N-1\leq M\leq N+777$
保证没有自环或重边。
### 部分分
$1$. $N,M\leq 100$（$9$ 分）
$2$. $N,M\leq 3000$（$7$ 分）
$3$. 保证该图是一棵树 （$12$ 分）
$4$. $N=M$ （$13$ 分）
$5$. $M-N\leq 7$，且保证图中存在一条顺次连接 $1,2,\dots,N$ 的链 （$28$ 分）
$6$. $M-N\leq 77$ （$22$ 分）
$7$. 无特殊条件 （$9$ 分）
