가장 어린 상사

어떤 회사의 지휘 계통에는 위원회도 이사회도 없다. 직원 사이의 관리 관계만 있고, 한 직원이 다른 직원을 관리하면서 동시에 또 다른 직원에게 관리받을 수 있다.

직원 P1이 직원 P2를 관리하는 형태는 두 가지다. P1이 P2의 바로 위 상급자면 P1은 P2를 직접 관리한다. P1이 어떤 직원 P3을 직접 관리하고 그 P3이 P2를 직접 또는 간접으로 관리하면, P1은 P2를 간접으로 관리한다. 어떤 직원도 자기 자신을 직접이나 간접으로 관리하지 않는다.

아래 그림은 직원 일곱 명의 지휘 계통과 각자의 나이다. (a)가 처음 상태고, (b)는 두 직원이 지휘 계통에서 자리를 맞바꾼 뒤의 상태다.

회사는 나이가 조직에서 어떤 역할을 하는지 알아보려고 지휘 계통을 분석하는 도구를 만들기로 했다. 도구는 명령을 주어진 순서대로 처리한다. 명령은 관리 변경과 질의, 두 종류다.

관리 변경 명령은 직원 A와 직원 B의 자리를 맞바꾼다. 지휘 계통의 자리와 자리 사이의 관리 관계는 그대로 남고, 두 직원이 자기 나이를 지닌 채 자리만 서로 옮긴다. A와 B가 같은 직원이면 아무것도 바뀌지 않는다.

질의 명령은 직원 E를 지정하고, 그 시점에 E를 직접 또는 간접으로 관리하는 직원 중 가장 어린 사람의 나이를 묻는다.

지휘 계통과 직원의 나이, 명령 목록이 주어질 때 모든 질의에 답하는 프로그램을 작성하시오.

첫 줄에 직원 수 $N$, 직접 관리 관계의 수 $M$, 명령의 수 $I$가 공백으로 구분되어 주어진다. 직원은 $1$번부터 $N$번까지 번호로 구분한다.

둘째 줄에 $N$개의 정수 $K_1, K_2, \dots, K_N$이 주어진다. $K_i$는 $i$번 직원의 나이다.

이어지는 $M$개 줄에는 두 정수 $X$와 $Y$가 주어진다. $X$가 $Y$를 직접 관리한다는 뜻이다.

그다음 $I$개 줄에는 명령이 한 줄에 하나씩 주어진다. 관리 변경 명령은 문자 T와 두 정수 $A$, $B$로 이루어지고, $A$번 직원과 $B$번 직원이 자리를 맞바꾼다. 질의 명령은 문자 P와 정수 $E$로 이루어지고, $E$번 직원을 관리하는 가장 어린 직원의 나이를 묻는다. 마지막 명령은 항상 질의다.

제약 조건

• $1 \le N \le 500$
• $0 \le M \le 60000$
• $1 \le I \le 500$
• $1 \le K_i \le 100$ ($1 \le i \le N$)
• $1 \le X, Y \le N$, $X \ne Y$
• $1 \le A, B \le N$
• $1 \le E \le N$
• 입력으로 주어지는 관리 관계에는 순환이 없다.

질의 명령마다 한 줄에 답을 출력한다. 지정된 직원을 직접 또는 간접으로 관리하는 직원이 있으면 그중 가장 어린 사람의 나이를 출력하고, 없으면 별표 하나(*)를 출력한다.