#P18396. Graph Cuts

Graph Cuts

Graph Cuts

给定一个无向图,没有重边或自环。另外维护一个初始为空的顶点集合 UU。依次处理以下操作:

  1. + v:把顶点 vv 加入 UU。保证此前 v∉Uv\notin U。
  2. - v:把顶点 vv 从 UU 移除。保证此前 v∈Uv\in U。
  3. ?:找到一条恰好有一个端点属于 UU 的边,并把它从图中永久删除;若不存在这样的边,则报告不存在。有多条符合条件的边时,可以任选一条。

输入格式

第一行包含两个整数 n,mn,m,分别表示图的顶点数和边数,0≤n,m≤1050\le n,m\le10^5。

接下来 mm 行,每行包含两个整数 u,vu,v,表示一条无向边的两个端点,1≤u,v≤n1\le u,v\le n。保证没有重边和自环。边按输入顺序从 1 到 mm 编号。

下一行包含一个整数 qq,表示操作数,0≤q≤1050\le q\le10^5。

接下来 qq 行,每行是一条上述格式的操作。操作中的顶点编号也满足 1≤v≤n1\le v\le n。

输出格式

对每条第三类操作输出一行:若选择了一条边,输出它的输入编号;若当前图中不存在符合条件的边,输出 0。

被输出的非零边必须仍在图中;一旦删除,后续任何集合操作都不会使它恢复。如果没有第三类操作,不输出任何内容。

原样例

4 5
1 2
1 3
1 4
2 3
2 4
10
+ 1
+ 2
?
?
?
?
?
- 2
?
?
5
4
3
2
0
1
0

样例输出只是一个合法选择序列,允许输出其他满足全部操作要求的序列。