← 返回题目列表

Codeforces · 2052/D

D. DAG 序列化

中文机器翻译题面 查看原题

考虑一个支持两种操作的简单单比特布尔寄存器:

  • 设置 — 将寄存器设置为 正确 如果是 假,并返回 正确;否则,它返回 假;
  • 未设置 — 将寄存器设置为 假 如果是 正确,并返回 正确;否则,它返回 假.

寄存器的初始状态是 假。假设有 $$$n$$$ 操作 $$$op_i$$$(对于 $$$1 \le i \le n$$$) 其中 最多两个操作返回 true。此外,我们还以有向无环图 (DAG) 的形式给出了操作的部分顺序:一条边 $$$i \rightarrow j$$$ 意味着 $$$op_i$$$ 之前发生过 $$$op_j$$$。系统会询问您是否可以将这些操作置于满足给定部分顺序的某种线性顺序中,并且如果按该顺序将操作应用于寄存器,则它们的结果与给定的结果相同。

输入

在第一行中,给你一个整数 $$$n$$$ — 操作次数 ($$$1 \le n \le 10^5$$$)。在下文中 $$$n$$$ 行,您将获得以下格式的操作:类型 结果“,其中 类型 是“设置“或”未设置”和 结果 是“正确“或”假“。保证最多有两个操作有”正确”结果。

在下一行中,您将获得一个整数 $$$m$$$ — DAG 的弧数 ($$$0 \le m \le 10^5$$$)。在下文中 $$$m$$$ 行,给你弧 — 整数对 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$; $$$a \neq b$$$)。每条弧线表示该操作 $$$op_a$$$ 在操作之前发生 $$$op_b$$$。

输出

打印满足 DAG 约束的任何线性操作顺序,并确保操作结果与输入中给出的结果匹配。如果不存在正确的操作顺序,则打印 $$$-1$$$.

示例

输入
复制

5
set true
unset true
set false
unset false
unset false
2
1 4
5 2

输出
复制

5 1 3 2 4 

输入
复制

3
unset true
unset false
set true
0

输出
复制

2 3 1 

输入
复制

2
unset false
set true
1
2 1

输出
复制

-1

输入
复制

2
unset false
set false
0

输出
复制

-1