[CEOI2017] One-Way Streets
题意：给定一个无向连通图，以及若干对点 (x, y)，要求给每条边定向，使得 x 能到达 y，求哪些边的方向是唯一确定的，并输出其方向。
环上的边方向不唯一
如果一条无向边 (u, v) 位于任何一个环中，那么它在环上的方向是可以灵活调整的。无论它指向 u -> v 还是 v -> u，环都能保证环上任意两点间有路径。
因此，这类边永远无法被强迫指向某一个特定方向，答案是 ‘B’（Both）。
所以，我们可以把所有不在环上的边（也就是桥）找出来，只有这些边才可能有唯一方向。
既然环上的边都是 “B”，我们可以把它们全部忽略，因为它们不贡献任何答案。
删除所有桥，剩下的每个连通块都是一个边双连通分量（内部任意两点间至少有两条边不相交的路径）。
将每个边双连通分量缩成一个点。
连接这些点的边，正好就是原图中的所有桥。缩点后，整个图会变成一棵树（或森林）。
至此，问题被完全转化到了树上。树上的每条边都对应原图的一座桥，是我们需要判断方向的候选对象。
现在，我们有一个限制条件 (x, y)，意思是原图中点 x 必须能到达点 y。
在缩点后的树中，x 和 y 所在的节点之间，有且仅有一条唯一路径。
为了让 x 能到达 y，这条路径上的所有边都必须指向从 x 到 y 的方向。
反向的边，以及路径之外的边，都不受这个条件影响。
当有多个限制条件时，每条边的方向将由覆盖它的所有路径共同决定。
如果一条边被某个路径要求指向 A -> B，又被另一个路径要求指向 B -> A，那么就会产生冲突，这条边的方向无法确定，答案是 ‘B’。
如果所有覆盖它的路径都要求指向同一个方向，那么这个方向就是唯一确定的。
如果没有任何路径经过这条边，它的方向也不确定，答案是 ‘B’。
计算答案：
我们需要高效地处理多条路径对树边的影响。树上差分正是解决这类问题的利器。
我们可以给每个树节点一个权值 diff，用它来统计经过该节点与其父节点之间这条边的路径信息：
标记路径：对于每个限制 (x, y)，我们做 diff[x] += 1，diff[y] -= 1（或在求LCA后做更标准的边差分，但核心思想一致）。这样做可以记录下路径的起点和终点。
自底向上累加：通过一次DFS，计算每个节点的子树 diff 值之和。这个累加和 sum[v] 代表了所有经过节点 v 与它父节点之间这条边的路径的净数量。
解读差分值：
如果 sum[v] > 0，说明从 v 子树方向到父节点方向的路径更多，因此边 (v, parent[v]) 应指向父节点方向。
如果 sum[v] < 0，说明从父节点方向到 v 子树方向的路径更多，边应指向子节点 v 方向。
如果 sum[v] == 0，说明没有路径覆盖这条边，或有正有负恰好抵消，但后者意味着存在冲突，因此方向不唯一。
[SCCPC 2026]环基基环树
题意：
你有一棵基环树（n 个点，n 条边，恰好一个环）。现在对这棵树进行变异操作：
每个点 u 变成一个长度至少为 3 的简单环 C_u
原图中的每条边 (u, v) 变成连接环 C_u 和环 C_v 之间的一条边
变异后得到一个新图。
现在给你这个变异后的图，请你还原出原来的基环树。
输出格式：输出还原后的基环树的点数和所有边。
变换后的图中有三类结构：
每个原图点扩展出来的简单环；
原图基环上的边，对应扩展环之间的非桥连接边；
原图基环外的树枝边，对应扩展环之间的桥。
因此，先找出所有桥并删去。
删去桥后：
每个扩展环内部的边仍然存在；
原图基环上的连接边仍然存在；
原图基环外的树枝连接边被删去。
删去桥后的度数性质
考虑删去桥后的图。
对于某个扩展环Cx：
如果环上的一个点没有承担原图基环上的连接边，那么它只和环上的左右
两个相邻点相连，度数为2；
如果环上的一个点承担了原图基环上的连接边，那么它除了两个环内邻点
外，还会连接到别的扩展环，度数至少为3。
由于原图是基环树，每个原图点在基环上至多有两条非桥连接边。又因
为cx ≥3，每个扩展环中一定存在度数为2的点
缩回一个扩展环
在删去桥后的图中，如果一个点的度数为2，那么它的两条边一定都是所在扩
展环的环内边。
因此，这个点和它的两个邻点一定来自原图中的同一个点，应当被缩成同一个
点。
不断利用这个性质，同一个扩展环上的点会被全部合并。
同时，不同扩展环之间的连接边不会导致错误合并，因为连接边的端点在删去
桥后的图中度数至少为3，不会作为度数为2的点去合并两侧。
按上述规则缩点后，每个缩点恰好对应原图中的一个点
还原原图边
完成缩点后，重新考虑变换后图中的每条边(u,v)。
设u 所在缩点为U，v 所在缩点为V。
若U =V，说明这条边是某个扩展环内部的边，不属于原图；
若U ̸ =V，说明这条边连接了两个扩展环，对应原图中的一条边。
因此，输出所有跨缩点的边，就得到还原后的基环树。
时间复杂度和空间复杂度均为O(n+m)。
