题目描述

给定一个网络路由图，包含$n$ 个节点（编号$1\sim n$）和$m$条无向边（编号$1\sim m$）。业务从源点$s$走到汇点$t$。 现发生$q$次故障，每次故障给出一个边编号$eid$，表示这条边失效，之后业务不能再经过它。 在每次故障发生后，需要输出“原始图中”（故障前）所有从$s$到$t$的简单路径中，有哪些路径被断开，并按以下方式编号输出：

1. 将所有$s\to t$ 的简单路径按「边编号序列」的字典序从小到大排序，依次编号为$1,2,\dots$；
2. 每次故障后，输出包含故障边的那些路径的编号（升序）。

题目内容

网络路由图由 $n$ 个点(编号从 $1$ 开始依次递增)和 $m$ 条边(编号从 $1$ 开始依次递增)构成，业务的流量由 $s$ 点走到 $t$ 点。

现在网络发生了 $q$ 次故障，每次故障给出一个整数 $i$ ，表示第 $i$ 条边发生了故障，业务将不能再经过这条边。

每次故障发生后，输出 $s$ 到 $t$ 的哪些简单路径被断开了。

$s$ 到 $t$ 的简单路径是一条点和边都不重复出现的路径。

$s$ 到 $t$ 的简单路径由一个边序列 $eid1,eid2,...,eidk$ 构成，$eid$ 代表 $edgeld$

为避免输出量过大，我们将原始图中的路径(故障发生前)按照边序列的字典序从小到大排序，依次编号为 $1,2,3,...$

每次故障发生后，只需要输出这些边的编号即可(从小到大排序)

在比较数组的字典序时，遵循以下规则：

1.从第一个元素开始，逐个比较数组对应位置的元素。

2.如果某个位置的元素不相同，较小的元素所在的数组排在前面。

3.如果所有比较位置的元素都相同，则较短的数组排在前面。

例如，给定两个数组 $[1,2,3]$ 和 $[1,2,4]$ ，由于在第三个位置上 $3< 4$ ，因此 $[1,2,3]$ 在字典序中排在 $[1,2,4]$ 之前。

如果比较 $[1,2]$ 和 $[1,2,0]$ ，由于前两个位置的元素相同，而第一个数组较短，因此 $[1,2]$ 在字典序中排在 $[1,2,0]$ 之前。

输入描述

第一行给出 $4$ 个整数 $n,m,s,t(2<=n<=500,1<=m<=1000,1<=s,t<=n,s<=t)$

第 $2$ 到 $m+1$ 行每行两个整数 $u,v$ 表示点 $u$ 和点 $v$ 之间有一条无向边,边按输入顺序编号为 $1,2,...,m$

第 $m+2$ 行给出一个整数 $q(1<=q<=m)$ 表示故障的发生次数

接下来 $q$ 行每行一个整数 $eid(edgeld)$ 表示编号为 $eld(1<=eld<=m)$ 的边发生了故障，保证所有的 $eld$ 互不相同

输入保证 $s$ 到 $t$ 的简单路径不超过 $1000000$ 条,保证以 $s$ 为起点不经过点 $t$ 的简单路径不超过 $10000000$ 条

输出描述

输出 $q$ 行，每行依次对应该次故障的答案

每行首先输出一个整数 $x$ 表示本次故障共有 $x$ 条路径被断开，接下来 $x$ 整数为这些被断开的路径的编号(升序输出)，单空格间隔

样例1

输入

2 2 1 2
1 2
1 2
2
2
1

输出

1 2
1 1

说明

样例2

输入

5 6 1 2
1 2
1 3
3 2
3 4
4 2
1 5
3
6
2
1

输出

0
2 2 3
1 1

说明

如图：

从 $1$ 到 $2$ 一共有 $3$ 条简单路径：$1->2，1->3->2，1->3->4->2$

$3$ 条路径的边序列分别为：$1$, $2$ $3$, $2$ $4$ $5$

因此按照字典序依次编号为：$1,2,3$

当断掉第 $6$ 条边 $(1->5)$，没有路径被断开

断掉第 $2$ 条边，路径 $2$ 和 $3$ 被断开

断掉第 $1$ 条边，路径 $1$ 被断开