맨해튼 정전

거대한 폭풍이 맨해튼을 휩쓸면서 송전선이 대거 끊어졌고, 여러 블록이 통째로 정전됐다. 1차 피해 조사에서 어떤 블록끼리 아직 송전선으로 이어져 있고 어떤 블록끼리 끊어졌는지 정리한 보고서가 나왔다. 두 블록이 송전선으로 이어져 있으면 한쪽 블록에 전기가 들어올 때 다른 쪽 블록에도 전기가 들어온다. 송전선은 가로나 세로로 인접한 블록 사이에만 놓을 수 있다. 자체 발전기가 있거나 외부 전원에 연결된 블록의 목록도 급히 만들었다.

격자 모양인 이 도시의 모든 블록에 다시 전기가 들어오도록 비상 송전선을 놓으려고 한다. 필요한 비상 송전선의 최소 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 정수 $n$, $m$, $p$, $c$가 주어진다. $n$, $m$ ($1 \le n, m \le 100$)은 도시의 가로 블록 수와 세로 블록 수이고, 도시는 $n \times m$ 블록으로 이루어진다. $p$ ($1 \le p \le n \cdot m$)는 발전기의 개수, $c$ ($1 \le c \le 2n \cdot m - n - m$)는 인접한 두 블록 사이에 살아남은 송전선의 개수다.
• 다음 $p$개 줄에 정수 $x$ ($0 \le x < n$)와 $y$ ($0 \le y < m$)가 주어진다. 블록 $(x, y)$에 자체 발전기가 있거나 그 블록이 외부 전원에 연결되어 있다는 뜻이다.
• 다음 $c$개 줄에 정수 $x$ ($0 \le x < n$), $y$ ($0 \le y < m$)와 문자 $d$가 주어진다. $d$는 R 또는 U다. $d$가 R이면 블록 $(x, y)$와 블록 $(x + 1, y)$ 사이에, $d$가 U이면 블록 $(x, y)$와 블록 $(x, y + 1)$ 사이에 송전선이 살아 있다. $x = n - 1$이면 $d$는 R일 수 없고, $y = m - 1$이면 $d$는 U일 수 없다.

각 테스트 케이스마다 모든 블록을 전원에 연결하는 데 필요한 비상 송전선의 최소 개수를 한 줄에 출력한다.