观察一下样例，不难发现答案单调不升。且注意到，一对点对 $(i,j)$ 至多贡献一次。

因此我们猜想，若 $G_k$ 中 $(i,j)$ 有贡献，则 $G_{k-1}$ 中 $(i,j)$ 仍有贡献。这不难证明（好像 [CSP-S 2021] 廊桥分配 也有这种思想）。

上述性质可以引出一个更强的判定条件，继续进行扩展，发现图 $G$ 中 $(i,j)(i\le j)$ 有贡献当且仅当存在两条路径 $P:i\to j,Q:j\to i$ 使得 $P,Q$ 中经过的编号最小的点编号 $\ge i$。

这条性质有点隐蔽，但证明非常简单，考虑反证法，假设有一个点 $k$ 在 $i\to j$ 的路径上，使得 $k\lt i$，那么就存在 $k\to j$ 和 $j\to i\to k$ 两条路径，则 $(k,j)$ 对答案产生贡献，$k$ 已被删除，与假设相悖。原命题成立。

然后我们考虑计算答案。根据上述性质，我们可以倒着加边，枚举判断每个点对最早在何时联通，然后后缀和计算答案。

但是这样是 $\mathcal O(n^2m)$ 的，考虑优化。

一种方法是直接倒序 Floyd，中途判断答案，但 $\mathcal O(n^3)$ 的复杂度很卡常，坏。

（不过这题数据比较水，其实也很难卡满复杂度，lg 题解中看到，似乎倒序加边跑 dijkstra，用斐波那契堆就可以过。）

考虑优化判断联通性的过程。枚举点 $i$，计算所有 $(i,j)(j\ge i)$ 的贡献。

发现 $(u,v)$ 在原图联通，等价于 $v$ 在原图和反图均可达 $u$。

将原图反图分开计算。先考虑原图上加入一条边 $u\to v$ 的影响。

发现若 $u,v$ 原本都与 $i$ 联通，则 $u\to v$ 这条边无意义，扔掉。

反之，若 $v$ 原本不联通，分情况讨论：

若 $u$ 原本联通，则 $v$ 本身和它所连的点变为联通状态。bfs 一遍即可。

反之，$u\to v$ 这条边以后可能产生贡献，先保存下来。

反图类似处理，显然 bfs 过程中答案会发生变化，途中计算即可。

不难发现这样每条边只会被遍历 1 次，故时间复杂度 $\mathcal O(n(n+m))$。稍有卡常，但问题不大。还有能完美通过本题的 bitset 做法，但是我学不会 /ll。

upd：新增了 bitset 的代码，具体做法可以去 Alex_Wei 老师的题解 中学习。