Manhattan Power Failure

A huge storm tore through Manhattan, destroying many power lines and leaving entire blocks without power. The first damage assessment produced a report showing which blocks are still connected by power lines and which are not. When two blocks are connected by a power line, one block having power means the other block has power too. A power line runs only between blocks that are adjacent horizontally or vertically. A quickly written list of the blocks that hold their own power generator, or that are connected to an external power source, is also available.

Emergency power lines have to go up so that every block of this grid city has power again. Find the smallest number of emergency power lines needed.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

• One line with four integers $n$, $m$, $p$, $c$. $n$ and $m$ ($1 \le n, m \le 100$) are how many blocks the city is wide and long, so the city has $n \times m$ blocks. $p$ ($1 \le p \le n \cdot m$) is the number of power generators, and $c$ ($1 \le c \le 2n \cdot m - n - m$) is the number of intact power lines between adjacent city blocks.
• $p$ lines, each with two integers $x$ ($0 \le x < n$) and $y$ ($0 \le y < m$), meaning that block $(x, y)$ has its own power source or is connected to an external power source.
• $c$ lines, each with two integers $x$ ($0 \le x < n$), $y$ ($0 \le y < m$) and a character $d$, where $d$ is R or U. If $d$ is R, an intact power line runs between block $(x, y)$ and block $(x + 1, y)$. If $d$ is U, it runs between block $(x, y)$ and block $(x, y + 1)$. If $x = n - 1$ then $d$ cannot be R, and if $y = m - 1$ then $d$ cannot be U.

For each test case, print one line with the smallest number of emergency power lines needed to connect every block to a power source.