给定一张图 $G$ 和其 DFS 生成树 $T$，记 $S_e$ 表示覆盖边 $e$ 的非树边集合，删去两条树边 $e_1,e_2$ 导致图不连通，当且仅当 $S_{e_1}=S_{e_2}$。

考虑分类讨论：

1. 删除一条边就不连通，这条边必定是没有被覆盖的边，容易统计。
2. 删除两条加入的边：不可能导致不连通。
3. 删一个原本边一个新加入的边：$(i,i+1)$ 删除后存在新加入的边，满足删除后不连通，当且仅当$(i,i+1)$ 被加入的边覆盖次数为 $1$，势能线段树维护覆盖次数，做全局数 $1$。
4. 删两个原本的边：$(i,i+1)(j,j+1)$删除后图不连通（$i\text{<}j$），当且仅当不存在一个边的其中一个端点在 $[i+1,j]$，另一个端点不在 $[i+1,j]$，这相当于覆盖 $(i,i+1)$ 的边集 $S_i$ 与覆盖 $(j,j+1)$ 的边集 S_j 相同。

对于第 $4$ 种情况，令 $S_i $为一个m位字符串，第 $i$ 位表示第 $i$ 个边是否覆盖 $i$，记 $lcp(i,j)$ 表示最大的时间 $t$ 满足 $S_i=S_j$，根据后缀排序的理论，只需要将每个 $i$ 的 $S$ 按照字典序排序，就只需要求出相邻的 $lcp$，然后即可按时间倒着做，并查集维护 $S$ 等价类合并。使用主席树维护 $S$ 的和哈希值，此时求 $lcp$ 的复杂度是双 $\log$，为二分版本序号加上树上查询，在套一层排序是 $3\log$。换维，主席树第 $i$ 个版本维护 $S_i$，扫描线求出所有版本，即可将求 $lcp$ 改为线段树二分做到单 $\log$，总复杂度双 $\log$。

比较器复杂度较高，因此用 std::stable_sort 更快。

Code

QOJ 的渲染好诡异。