미토콘드리아 이브

미토콘드리아 DNA는 생물의 세포 안에 있는 미토콘드리아가 가진 DNA 분자이다.

이 DNA는 오직 모계(어머니 쪽)로만 유전된다. 그래서 전 인류에게는 하나의 공통 모계 조상, 이른바 "미토콘드리아 이브"가 존재한다. 모계 조상이란 가계도에서 어머니, 그 어머니의 어머니처럼 여성 쪽 선만 따라 거슬러 올라갈 때 만나는 조상을 말한다. 예를 들어 어머니와 외할머니는 모두 모계 조상이다.

인류의 미토콘드리아 이브는 약 20만 년 전 동아프리카에 살았던 것으로 추정된다.

이 문제에서는 이형 접합을 하는 진핵 생물 한 종으로 이루어진 어떤 집단을 다룬다. 연구자들은 이 집단의 개체 수 변화를 시간 순서대로 빠짐없이 기록했고, 그중 일부 개체의 미토콘드리아 DNA를 서열 분석했다. 관찰 대상 집단에서 미토콘드리아 DNA는 모계로 유전될 때 돌연변이 없이 그대로 전달된다고 가정한다.

관찰이 끝난 시점에 살아 있는 모든 개체가 서로 같은 미토콘드리아 DNA를 가지는지 판별하는 프로그램을 작성하시오.

첫째 줄에 관찰을 시작한 시점에 살아 있던 개체의 수를 나타내는 정수 $n$ ($1 \le n \le 100000$)이 주어진다. 이 개체들의 ID는 $1$부터 $n$까지의 정수이다.

이어지는 $n$개의 줄에는 각 줄마다 문자 하나가 주어진다. $i$번째 줄의 문자는 ID가 $i$인 개체의 성별이며, M은 수컷, F는 암컷을 뜻한다.

그다음 줄에는 관찰 기간 동안 일어난 출생과 사망 사건의 총 횟수를 나타내는 정수 $m$ ($0 \le m \le 100000$)이 주어진다.

이어지는 $m$개의 줄에는 출생과 사망 정보가 시간 순서대로 주어진다.

• 출생은 세 개의 값으로 주어지며, 순서대로 아버지의 ID, 어머니의 ID, 새끼의 성별(M 또는 F)이다. 새로 태어난 개체의 ID는 그때까지 한 번도 ID로 쓰인 적 없는 가장 작은 양의 정수이다.
• 사망은 음수 하나로 주어지며, 죽은 개체의 ID 앞에 마이너스 부호를 붙인 값이다.

그다음 줄에는 서열 분석된 미토콘드리아 DNA의 개수를 나타내는 정수 $k$ ($0 \le k \le n + m$)가 주어진다.

이어지는 $k$개의 줄에는 각 줄마다 공백으로 구분된 두 정수가 주어진다. 앞의 값은 미토콘드리아 DNA를 분석한 개체의 ID이고, 뒤의 값은 그 DNA의 고유 식별 번호이다. 두 DNA의 고유 식별 번호가 같다는 것은 두 DNA가 같다는 것과 동치이다. 고유 식별 번호는 $1$ 이상 $10^9$ 이하의 정수이다.

주어지는 모든 데이터는 서로 모순되지 않으며, 한 개체의 미토콘드리아 DNA는 많아야 한 번만 분석된다. 관찰이 끝난 시점에 적어도 한 개체는 살아 있다.

한 단어를 출력한다.

• YES — 관찰이 끝난 시점에 살아 있는 모든 개체가 같은 미토콘드리아 DNA를 가지는 것이 확실한 경우.
• NO — 살아 있는 개체들 중 서로 다른 미토콘드리아 DNA를 가진 개체가 있는 것이 확실한 경우.
• POSSIBLY — 주어진 정보만으로는 YES인지 NO인지 확정할 수 없는 경우.