#P18396. Graph Cuts
Graph Cuts
Graph Cuts
给定一个无向图,没有重边或自环。另外维护一个初始为空的顶点集合 。依次处理以下操作:
+ v:把顶点 加入 。保证此前 。- v:把顶点 从 移除。保证此前 。?:找到一条恰好有一个端点属于 的边,并把它从图中永久删除;若不存在这样的边,则报告不存在。有多条符合条件的边时,可以任选一条。
输入格式
第一行包含两个整数 ,分别表示图的顶点数和边数,。
接下来 行,每行包含两个整数 ,表示一条无向边的两个端点,。保证没有重边和自环。边按输入顺序从 1 到 编号。
下一行包含一个整数 ,表示操作数,。
接下来 行,每行是一条上述格式的操作。操作中的顶点编号也满足 。
输出格式
对每条第三类操作输出一行:若选择了一条边,输出它的输入编号;若当前图中不存在符合条件的边,输出 0。
被输出的非零边必须仍在图中;一旦删除,后续任何集合操作都不会使它恢复。如果没有第三类操作,不输出任何内容。
原样例
4 5
1 2
1 3
1 4
2 3
2 4
10
+ 1
+ 2
?
?
?
?
?
- 2
?
?
5
4
3
2
0
1
0
样例输出只是一个合法选择序列,允许输出其他满足全部操作要求的序列。