DAG 직렬화

시간 제한3초메모리 제한2048 MB

요약

방향 비순환 그래프의 선후 관계를 지키면서 set과 unset 연산의 반환값이 모두 맞도록 실행 순서를 정하고, 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 위상 정렬, 그래프, 구현
정답자: 아직 제출이 없습니다

문제

단일 비트 불리언 레지스터는 두 가지 연산을 지원한다.

set: 레지스터가 false였다면 true로 바꾸고 true를 반환한다. 그렇지 않으면 false를 반환한다.
unset: 레지스터가 true였다면 false로 바꾸고 true를 반환한다. 그렇지 않으면 false를 반환한다.

레지스터의 초기 상태는 false이다. $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$ 줄에는 type result 형식으로 각 연산이 주어진다. type은 set 또는 unset이고, result는 true 또는 false이다. 결과가 true인 연산은 최대 두 개라고 보장된다.

다음 줄에는 DAG의 간선 개수 $m$ 이 주어진다 ( $0 \le m \le 10^5$ ). 다음 $m$ 줄에는 두 정수 $a$ 와 $b$ ( $1 \le a, b \le n$ ; $a \neq b$ )가 주어진다. 이는 $op\_a$ 가 $op\_b$ 보다 먼저 일어났다는 뜻이다.

출력

DAG 조건을 지키고 주어진 결과와 일치하는 연산 순서를 하나 출력한다. 그런 순서가 없으면 $-1$ 을 출력한다.

예제4

예제 1

입력

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

예상 출력

5 1 3 2 4

예제 2

입력

3
unset true
unset false
set true
0

예상 출력

2 3 1

예제 3
입력
```
2
unset false
set true
1
2 1
```
예상 출력
```
-1
```
예제 4
입력
```
2
unset false
set false
0
```
예상 출력
```
-1
```