1. 题意理解 我们有：

$n$ 个点，坐标 $(x_i, y_i)$ 在矩形 $(0,0)$ 到 $(A,B)$ 内。

如果 $x_i = 0$，称为西侧点。

如果 $x_i = A$，称为东侧点。

$m$ 条边，有向或无向，除了在端点外不相交（即平面图）。

问题：对每个西侧点，求它能沿着边到达多少个东侧点。

输出时，按西侧点的 $y$ 从大到小输出结果。

2. 关键点分析 2.1 平面图性质 题目说“边在交点以外的任何地方不相交”，意味着这是一个平面图。 平面图的一个重要性质是：它的对偶图（或者某种定向）可以给出路径的偏序关系。

2.2 东西侧的特殊性 西侧点都在 $x=0$ 上，东侧点都在 $x=A$ 上。

矩形边界可能没有显式给出作为边，但图是画在矩形内的，所以西侧和东侧在某种意义上像是“源”和“汇”。

3. 思路推导 这个问题等价于： 对每个西侧点 $S$，求东侧点的可达集合大小。

直接做 $n$ 次 BFS/DFS 会超时（$n, m$ 可达 $3\times 10^5, 9\times 10^5$）。

3.1 平面图的可达性技巧 在平面图中，如果所有边不相交，那么我们可以利用“左右”关系来简化问题。

一个常见技巧：

把图的外边界看作一个环，西侧和东侧分别是环上的一段。

在平面图中，从西侧到东侧的路径会按照某种“从上到下”的顺序排列。

3.2 转化为“区间覆盖” 想象把矩形拉成一个长条，西侧在左，东侧在右。 平面图保证：如果我们按 $y$ 坐标给西侧点编号 $S_1, S_2, \dots, S_k$（从上到下），给东侧点编号 $T_1, T_2, \dots, T_l$（从上到下），那么：

从 $S_i$ 能到达的东侧点，在 $T$ 序列中是一个连续区间。

为什么？ 因为如果 $S_i$ 能到达 $T_a$ 和 $T_c$（$a < c$），那么它也能到达中间的 $T_b$（$a < b < c$），否则路径会交叉，违反平面图性质（Jordan曲线定理的一种形式）。

3.3 利用区间简化问题 因此，问题变成：

对每个西侧点 $S_i$，求它能到达的东侧点的区间 $[L_i, R_i]$，然后答案就是 $R_i - L_i + 1$。

3.4 如何求区间 我们可以用动态规划/记忆化搜索在平面图结构上递推：

把图拆成面（faces），利用平面图的对偶图。

另一种方法：按拓扑序处理（如果有向图无环），但这里可能有环（无向边），所以不能直接拓扑。

更实际的方法：

把无向边视为双向边。

从所有东侧点反向 BFS/DFS，标记能到达东侧点的节点。

但这样只能判断能否到达任意东侧点，不能得出区间。

为了得到区间，需要更精细的方法：

从上到下扫描西侧点，利用平面图路径不交叉的性质，维护当前能到达的东侧点的最小和最大索引。

3.5 具体算法（概念） 把西侧点按 $y$ 降序排序，东侧点也按 $y$ 降序排序，并编号。

构建图时，把无向边当作两条有向边。

用 BFS 或 DFS 从每个西侧点出发，但利用单调性优化： 如果 $S_i$ 能到达的区间是 $[L_i, R_i]$，那么 $S_{i+1}$（在它下面）的区间很可能与 $S_i$ 有重叠，可以利用之前的信息。

实际上，可以一次 BFS 从所有西侧点开始，但给每个节点记录它能到达的东侧点的最小和最大编号（min-index, max-index），通过边更新。

由于是平面图，更新时不会出现矛盾（即不会出现交叉路径导致区间不连续）。

3.6 实现细节（不写代码，但描述） 初始化：每个东侧点 $T_j$ 的区间是 $[j, j]$，西侧点初始区间为 $[\infty, -\infty]$。

用 BFS 或 DFS（或多次迭代，因为可能有环）来传播区间： 对边 $u \to v$，用 $u$ 的区间更新 $v$ 的区间（取并集）。

因为无向边，要双向传播，但注意方向性：有向边只能沿方向传播。

迭代直到区间不再变化。

最后对每个西侧点，区间长度就是答案。

4. 时间复杂度 每个点维护两个整数（min, max）。

更新时，如果区间扩大才继续传播。

最坏情况下每个边被激活 $O(\text{区间大小})$ 次，但平面图边数 $O(n)$，区间大小不超过东侧点数，所以可接受。

实际可用 BFS 队列优化。

5. 总结 核心思想：

利用平面图路径不交叉的性质，把可达集合变成连续区间。

通过 BFS/DFS 传播区间（min, max）来高效计算。

按 $y$ 降序输出西侧点的结果。

这样就能在 $O(n + m)$ 的近似复杂度内解决问题，适用于大数据范围。