그래프의 종착지

시간 제한2초메모리 제한1024 MB

요약

각 노드가 자식 중 하나를 가리키며 등급이 있는 그래프에서, 시작 노드에서 내려가며 포인터가 순환할 때 T번째 턴의 마지막 노드를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 수학, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

디미고에서 공부가 너무나도 하기 싫었던 ecode는 야자 시간에 의미 없는 그래프를 그렸다. 어떻게든 자신이 만든 그래프에 의미를 부여하고 싶었던 ecode는 아래와 같은 규칙을 덧붙였다.

그래프의 모든 노드는 번호와 등급이 존재한다.
같은 등급의 노드 사이에는 간선이 존재하지 않는다.
$1$ 등급 노드는 한 개만 존재한다.
어떤 노드에 연결된 하위 등급의 노드를 "자식 노드"라고 하자. 자식 노드가 존재하는 모든 노드는 자식 노드 중 하나를 가리키고 있다.

이러한 규칙에 따라 작성한 결과 아래와 같은 그래프를 얻었다.

옆에서 이를 지켜보던 ecode의 짝꿍인 oh051525는 이를 한심하게 쳐다보며 말하였다.

차라리 이 그래프로 게임까지 만들어버리지 그래?

광기가 서린 ecode는 그녀의 아이디어에 감탄하며 이 그래프로 게임을 만들어버렸다!!

ecode가 만든 게임은 출발 지점에서 시작해 그래프의 간선을 따라 이동하는 게임이다. 게임의 한 턴은 다음과 같이 진행된다.

플레이어는 $1$ 등급 노드에서 시작한다.
플레이어가 현재 위치한 노드 $v$ 의 자식 노드가 존재한다면, $v$ 가 가리키는 자식 노드 $w$ 의 위치로 이동한 뒤 다음과 같은 규칙으로 $v$ 가 자신의 자식 노드를 가리키도록 한다.
- $w$ 의 번호가 $v$ 의 자식 노드의 번호 중 가장 큰 값이 아니라면, $v$ 는 $w$ 보다 큰 번호를 가지는 것들 중 번호가 가장 작은 자식 노드를 가리키게 된다.
- $w$ 의 번호가 $v$ 의 자식 노드의 번호 중 가장 큰 값이라면, $v$ 는 가장 작은 번호를 가진 자식 노드를 가리키게 된다.
플레이어가 현재 위치한 노드 $v$ 의 자식 노드가 존재하지 않는다면, 턴을 종료한다.

ecode는 친구들과의 대결에서 승리하기 위해, $T$ 번째 턴에 마지막으로 도착한 노드의 번호를 미리 알아내려고 한다. 게임의 답을 최대한 빨리 알고 싶은 ecode를 위해 이를 해결하는 코드를 작성해 보자!

입력

첫 번째 줄에 노드의 개수 $N$ 과 간선의 개수 $K$ , 작업의 실행 횟수 $T$ 가 주어진다. $(1\leq N\leq 10^5;$ $0\leq K\leq 3\times 10^5;$ $1\leq T\leq 5\times 10^5)$

두 번째 줄부터 $K$ 개의 줄에 걸쳐, 간선으로 연결된 두 노드의 번호 $x$ 와 $y$ 가 공백으로 구분되어 주어진다.

$K+2$ 번째 줄에 각 노드의 등급을 나타내는 $N$ 개의 정수 $A\_1, A\_2, ..., A\_N$ 가 공백으로 구분되어 주어진다. $A\_i$ 는 $i$ 번 노드의 등급을 의미한다. $(1\leq A\_i\leq 5\times 10^5)$ $1$ 등급 노드는 항상 한 개 존재한다.

$K+3$ 번째 줄에 $i$ 번 노드의 화살표가 가리키는 하위 등급 노드의 번호가 공백으로 구분되어 주어진다. $i$ 번 노드에 연결된 하위 등급 노드가 없다면 $-1$ 이 입력된다.

게임의 규칙을 어기는 경우는 입력으로 주어지지 않는다.

출력

$T$ 번째 턴에 마지막으로 도착한 노드의 번호를 출력한다.

예제2

예제 1

입력

15 19 2
1 2
2 3
3 9
10 4
2 10
4 2
11 9
11 8
12 11
4 11
10 12
1 5
5 15
5 12
6 5
6 1
7 6
14 13
7 13
1 2 3 4 3 2 3 6 4 3 5 6 5 6 4
2 4 9 11 12 5 13 -1 11 4 12 -1 14 -1 -1

예상 출력

예제 2

입력

10 11 5
3 2
4 7
8 10
5 3
1 2
8 5
5 7
3 4
4 6
3 1
7 9
1 2 3 4 5 8 8 7 12 11
2 3 5 6 8 -1 9 10 -1 -1

예상 출력