星途勘测__牛客网

在宇宙一隅被遗忘的星域中，流传着一张古老的星图。这张图上描绘了 $n$ 颗恒星，它们之间由 $m$ 条被称为“星途”的古代航道相连。千百年来，无数的朝圣者沿着这些星途，从启程之星 $s$ 前往圣地之星 $t$ 。古代的天文学家们以其惊人的严谨，将每一条可行的朝圣路线都记录在了一部伟大的星图法典之中。

这张星图可以被抽象为一个无向图 $G = (V, E)$ ，其中：
$V = \{1, 2, \dots, n\}$ 是恒星的集合，每颗恒星都有一个从 $1$ 到 $n$ 的唯一编号。
$E = \{1, 2, \dots, m\}$ 是星途的集合，每条星途同样有一个从 $1$ 到 $m$ 的唯一编号。

一次合法的朝圣之旅是一条从恒星 $s$ 到恒星 $t$ 的**简单路径**。这意味着，在这条路径上，任何一颗恒星或任何一条星途都不能被重复经过。每一条朝圣路线都可以通过其经过的星途编号序列来唯一确定，我们将其表示为 $P = \langle e_1, e_2, \dots, e_k \rangle$ 。

为了编纂这部权威的法典，古代天文学家们将所有可能的朝圣路线 $P$ ，按照其星途编号序列的**字典序**进行了升序排列。排序后，每一条路线都被赋予了一个从 $1$ 开始的唯一索引。

如今，一连串的 $q$ 场宇宙风暴正席卷这片星域。每场风暴都会精准地袭击并摧毁一条星途，使其无法通行。对于每一次风暴事件，你的任务是查阅法典，并报告出所有被此次风暴所切断的朝圣路线的索引。

输入数据描述了星图的结构和宇宙风暴的序列。

1. 第一行包含四个整数 $n, m, s, t$ 。
* $n$ ：恒星的数量 ( $2 \le n \le 500$ )。
* $m$ ：星途的数量 ( $1 \le m \le 1000$ )。
* $s, t$ ：启程之星与圣地之星的编号 ( $1 \le s, t \le n, s \neq t$ )。
2. 接下来的 $m$ 行，每行包含两个整数 $u, v$ ，表示在恒星 $u$ 和 $v$ 之间存在一条双向的星途。这些星途按照输入顺序，依次被编号为 $1, 2, \dots, m$ 。
3. 之后的一行是一个整数 $q$ ( $1 \le q \le m$ )，代表宇宙风暴的总次数。
4. 最后 $q$ 行，每行包含一个整数 $e_{id}$ ( $1 \le e_{id} \le m$ )，代表本次风暴中被摧毁的星途的编号。保证每次风暴袭击的星途都不同。

**约束条件**：题目保证从 $s$ 到 $t$ 的简单路径总数不超过 $1,000,000$ 条。

针对 $q$ 次风暴，你需要输出 $q$ 行答案。

每一行对应一次风暴的结果，格式如下：首先输出一个整数 $x$ ，代表因此次风暴而被切断的路线总数；随后是 $x$ 个整数，代表这些被切断路线在法典中的索引（需按升序排列），数字之间以单个空格分隔。

说明

*   星图中有两条连接恒星1和2的星途，编号分别为1和2。
*   因此存在两条路线，按字典序排列后，路线1（只走星途1）索引为1，路线2（只走星途2）索引为2。
*   风暴1摧毁星途2，切断了索引为2的路线。
*   风暴2摧毁星途1，切断了索引为1的路线。

说明

星图法典中记载了3条从恒星1到2的路线。按其星途序列的字典序排序后：
1.  **路线索引 1**: 
2.  **路线索引 2**: 
3.  **路线索引 3**: 

*   **风暴 1**: 摧毁星途 。此星途不在任何一条路线中，故无影响。输出 `0`。
*   **风暴 2**: 摧毁星途 。路线索引为  和  的两条路线均使用了此星途，故被切断。输出 `2 2 3`。
*   **风暴 3**: 摧毁星途 。路线索引为  的路线被切断。输出 `1 1`。

星途勘测

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题