DAG Serialization

Time limit3sMemory limit2048 MB

Summary

Order n set and unset operations under DAG precedence so each returned result matches a register that starts false, or print -1.

Level: Medium6 of 10
Topics: Topological sort, Graph, Implementation
Solved: No attempts yet

Problem

A single-bit boolean register supports two operations:

set: sets the register to true if it was false, and returns true. Otherwise, it returns false.
unset: sets the register to false if it was true, and returns true. Otherwise, it returns false.

The initial state of the register is false. There are $n$ operations $op\_i$ (for $1 \le i \le n$ ), and at most two of them return true. The order constraints form a directed acyclic graph (DAG): an edge $i \rightarrow j$ means that $op\_i$ happened before $op\_j$ . Determine whether the operations can be arranged in a linear order that respects these constraints and produces the given results when applied to the register in that order.

Input

The first line contains an integer $n$ , the number of operations ( $1 \le n \le 10^5$ ). Each of the next $n$ lines contains an operation in the format type result. Here type is set or unset, and result is true or false. It is guaranteed that at most two operations have the result true.

The next line contains an integer $m$ , the number of arcs in the DAG ( $0 \le m \le 10^5$ ). Each of the next $m$ lines contains two integers $a$ and $b$ ( $1 \le a, b \le n$ ; $a \neq b$ ), meaning that $op\_a$ happened before $op\_b$ .

Output

Print any linear order of the operations that satisfies the DAG constraints and matches the given results. If no such order exists, print $-1$ .

Examples4

Example 1

Input

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

Expected output

5 1 3 2 4

Example 2

Input

3
unset true
unset false
set true
0

Expected output

2 3 1

Example 3
Input
```
2
unset false
set true
1
2 1
```
Expected output
```
-1
```
Example 4
Input
```
2
unset false
set false
0
```
Expected output
```
-1
```