30831번 - 선후수과목

문제

서울시립대학교에는 숨겨진 특수 학과가 존재한다. 바로 이루매를 위한 비행학과다.

비행학과의 과목 이수 체계도는 과목들을 두 가지 관계를 이용해 표현한다.

• 권장 선후수 관계: 두 과목 사이에 권장되는 선수-후수 관계를 표현한다. 즉, 후수 과목을 수강하기 위해서 선수 과목을 반드시 수강할 필요가 없다.
• 필수 선후수 관계: 두 과목 사이에 필수적인 선수-후수 관계를 표현한다. 즉, 후수 과목을 수강하기 위해서 선수 과목을 반드시 수강해야 한다.

주어지는 과목 이수 체계도는 다음과 같은 규칙을 갖는다.

• 모든 과목은 0 또는 1개의 후수 과목을 갖는다.
• 모든 과목은 0 또는 1개의 필수 선수 과목을 갖는다.
• 두 과목 사이에는 권장 선후수 관계, 필수 선후수 관계 중 한 가지 관계가 있거나, 아무런 관계도 없다.
• 임의의 과목에 대하여, 후수 과목을 거쳐 계속 과목을 선택하였을 때 같은 과목을 두 번 이상 선택할 수 없다.

이 학과는 특수한 학과라 한 학기에 최대 한 과목만 수강할 수 있다. 이루매는 똑똑해서 각 학기마다 수강하고 싶은 과목을 미리 선택한 후 다음과 같은 규칙을 적용해 최종적으로 수강할 과목을 선택하고자 한다.

• 이미 수강한 과목은 다시 수강할 수 없어서 선택할 수 없다. 대신 이루매는 그 과목의 후수 과목을 선택한다. 만약 후수 과목이 없다면 해당 학기는 아무 과목도 수강하지 않기로 하고 과목 선택을 멈춘다.
• 선택한 과목의 수강하지 않은 필수 선수 과목이 있다면 그 과목은 아직 수강할 수 없다. 대신 선택한 과목의 필수 선수 과목을 선택한다.
• 위 규칙을 수강이 가능한 과목이 선택되거나 아무 과목도 수강하지 않기로 할 때까지 반복한다.

이루매는 위 과정 끝에 선택된 과목을 수강한다. 단, 수강할 수 있는 과목이 없는 경우 이루매는 아무런 과목도 수강하지 않는다.

이루매가 각 학기마다 수강하고자 하는 과목이 주어질 때, 이루매가 실제로 수강하게 되는 과목을 알려주고 수강하게 해 주자!

입력

첫 번째 줄에 과목 이수 체계도에 포함된 과목의 수 $N,ドル 권장 선후수 관계의 수 $A,ドル 필수 선후수 관계의 수 $B$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1\ 000\ 000; \ 0 \leq A, B; \ A+B \leq N-1)$

다음 $A$개의 줄에 권장 선후수 관계를 나타내는 과목 번호 $a, b$가 공백으로 구분되어 주어진다. $a$가 선수 과목, $b$가 후수 과목이다. $(1 \leq a, b \leq N)$

다음 $B$개의 줄에 필수 선후수 관계를 나타내는 과목 번호 $c, d$가 공백으로 구분되어 주어진다. $c$가 선수 과목, $d$가 후수 과목이다. $(1 \leq c, d \leq N)$

다음 줄에 이루매가 수강하는 학기의 수 $S$가 주어진다. $(1 \leq S \leq 1\ 000\ 000)$

다음 $S$개의 줄에 각 학기마다 이루매가 처음 선택한 과목 번호 $e$가 주어진다. $(1 \leq e \leq N)$

출력

$S$개의 줄에 각 학기마다 수강하게 되는 과목 번호를 출력한다. 이때 수강하게 되는 과목이 없다면 -1을 출력한다.

주어지는 각 학기는 독립적이지 않다. 즉, 어떤 과목을 실제로 수강하게 된다면 그 다음 학기부터 그 과목은 수강한 상태로 처리하여야 한다.

제한

힌트