선후수과목
시간 제한2초메모리 제한1024 MB
후수 과목이 최대 하나인 그래프에서, 각 학기마다 수강하려는 과목 후수 및 필수 선수 사슬을 따라가 실제로 수강할 과목을 찾고 수강 이력을 갱신한다.
문제
서울시립대학교에는 숨겨진 특수 학과가 존재한다. 바로 이루매를 위한 비행학과다.
비행학과의 과목 이수 체계도는 과목들을 두 가지 관계를 이용해 표현한다.
- 권장 선후수 관계: 두 과목 사이에 권장되는 선수-후수 관계를 표현한다. 즉, 후수 과목을 수강하기 위해서 선수 과목을 반드시 수강할 필요가 없다.
- 필수 선후수 관계: 두 과목 사이에 필수적인 선수-후수 관계를 표현한다. 즉, 후수 과목을 수강하기 위해서 선수 과목을 반드시 수강해야 한다.
주어지는 과목 이수 체계도는 다음과 같은 규칙을 갖는다.
- 모든 과목은 0 또는 1개의 후수 과목을 갖는다.
- 모든 과목은 0 또는 1개의 필수 선수 과목을 갖는다.
- 두 과목 사이에는 권장 선후수 관계, 필수 선후수 관계 중 한 가지 관계가 있거나, 아무런 관계도 없다.
- 임의의 과목에 대하여, 후수 과목을 거쳐 계속 과목을 선택하였을 때 같은 과목을 두 번 이상 선택할 수 없다.
이 학과는 특수한 학과라 한 학기에 최대 한 과목만 수강할 수 있다. 이루매는 똑똑해서 각 학기마다 수강하고 싶은 과목을 미리 선택한 후 다음과 같은 규칙을 적용해 최종적으로 수강할 과목을 선택하고자 한다.
- 이미 수강한 과목은 다시 수강할 수 없어서 선택할 수 없다. 대신 이루매는 그 과목의 후수 과목을 선택한다. 만약 후수 과목이 없다면 해당 학기는 아무 과목도 수강하지 않기로 하고 과목 선택을 멈춘다.
- 선택한 과목의 수강하지 않은 필수 선수 과목이 있다면 그 과목은 아직 수강할 수 없다. 대신 선택한 과목의 필수 선수 과목을 선택한다.
- 위 규칙을 수강이 가능한 과목이 선택되거나 아무 과목도 수강하지 않기로 할 때까지 반복한다.
이루매는 위 과정 끝에 선택된 과목을 수강한다. 단, 수강할 수 있는 과목이 없는 경우 이루매는 아무런 과목도 수강하지 않는다.
이루매가 각 학기마다 수강하고자 하는 과목이 주어질 때, 이루매가 실제로 수강하게 되는 과목을 알려주고 수강하게 해 주자!
입력
첫 번째 줄에 과목 이수 체계도에 포함된 과목의 수 , 권장 선후수 관계의 수 , 필수 선후수 관계의 수 가 공백으로 구분되어 주어진다.
다음 개의 줄에 권장 선후수 관계를 나타내는 과목 번호 가 공백으로 구분되어 주어진다. 가 선수 과목, 가 후수 과목이다.
다음 개의 줄에 필수 선후수 관계를 나타내는 과목 번호 가 공백으로 구분되어 주어진다. 가 선수 과목, 가 후수 과목이다.
다음 줄에 이루매가 수강하는 학기의 수 가 주어진다.
다음 개의 줄에 각 학기마다 이루매가 처음 선택한 과목 번호 가 주어진다.
출력
개의 줄에 각 학기마다 수강하게 되는 과목 번호를 출력한다. 이때 수강하게 되는 과목이 없다면 -1을 출력한다.
주어지는 각 학기는 독립적이지 않다. 즉, 어떤 과목을 실제로 수강하게 된다면 그 다음 학기부터 그 과목은 수강한 상태로 처리하여야 한다.