피그파티트 기린

두 개의 울타리가 나란히 있다. 한쪽에는 돼지 무리가, 다른 쪽에는 기린 떼가 산다. 돼지는 기린에게 갈 수 없고, 기린도 돼지에게 갈 수 없지만 울타리 너머로 대화할 수 있다. 이들은 아주 가까운 친구여서, 돼지는 다른 돼지보다 기린과 대화하기를 좋아하고, 기린도 다른 기린보다 돼지와 대화하기를 좋아한다.

이 관계는 상호적이다. 어떤 돼지가 특정 기린과 대화하기를 좋아하면, 그 기린도 같은 돼지와 대화하기를 좋아한다. 돼지끼리 대화하기를 좋아하는 경우는 없고, 기린끼리 대화하기를 좋아하는 경우도 없다.

동물이 다른 동물에게 메시지를 보내고 싶으면, 직접 대화하기를 좋아하지 않더라도 다른 동물을 거쳐 전달할 수 있다. 메시지는 서로 대화하기를 좋아하는 동물끼리만 전달된다.

두 동물 사이의 소음 수준은 출발 동물에서 도착 동물까지 메시지를 전달하는 데 필요한 대화 횟수의 최솟값이다. 두 동물 사이에 메시지를 전달할 수 없으면 소음 수준은 $0$이다. 예를 들어 두 동물이 직접 대화하기를 좋아하면 소음 수준은 $1$이다. 다른 동물 한 마리를 거쳐야 하면 $2$이고, 이런 식으로 계속된다.

전체 소음 수준은 서로 다른 동물의 모든 비순서쌍에 대한 소음 수준의 합이다. 각 쌍은 한 번만 센다.

동물의 수는 계속 늘어난다. 새 동물은 같은 종류의 기존 동물 두 마리를 부모로 하여 태어난다. 새 동물은 부모와 같은 종류(돼지 또는 기린)가 되며, 태어나자마자 다른 동물과 대화를 시작할 수 있다.

새 동물은 부모 중 정확히 한 마리와만 대화하기를 좋아하는 동물과 대화하기를 좋아한다. 초기 설정 후에 동물의 탄생을 나타내는 질의 수열이 주어진다. 각 탄생 후의 전체 소음 수준을 계산한다.

첫 줄에 세 정수 $A$, $B$, $M$($1 \le A, B \le 8$, $0 \le M \le A \cdot B$)이 주어진다. 각각 돼지의 수, 기린의 수, 서로 대화하기를 좋아하는 초기 쌍의 수이다.

다음 $M$개의 줄에는 두 정수 $0 \le a < A$, $0 \le b < B$가 주어지며, 돼지 $a$가 기린 $b$와 대화하기를 좋아한다는 뜻이다.

다음 줄에는 정수 $Q$($1 \le Q \le 10^5$)가 주어지며, 새로 태어날 동물의 수이다. 이어지는 $Q$개의 줄에는 문자 X와 두 정수 $p$, $q$가 주어진다. X는 A 또는 B이며, 태어나는 동물이 돼지인지 기린인지를 나타낸다. $p$와 $q$는 부모의 번호이다. 새 동물은 같은 종류 중에서 사용되지 않은 가장 작은 양의 번호를 받는다. $p$와 $q$는 항상 이미 존재하는 동물을 가리킨다고 보장된다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 동물이 태어난 뒤의 전체 소음 수준을 출력한다.