Flipping Networks

The Dean of the Unseen University has decided to modernise his communication by installing a computer network of bidirectionally connected hosts, numbered consecutively from $1$ to $h$. Because the environment is intensely magical, the structure of the network changes at random, and often.

It is therefore valuable to know which hosts can be reached from the main host and which cannot. These structural changes can be monitored without disturbing the network, so the current state of the network is known at any moment.

By convention, any host that can be reached from the main host (host $1$) in $10$ hops or fewer is called online. Some hosts may be reachable from host $1$ and still not be online, because every path connecting them to host $1$ is longer than $10$ hops. The Dean wants to know how many such hosts exist.

The first line contains a single integer: the number of test cases. Each test case has the following format:

• One line with an integer $h$, the number of hosts ($1 \le h \le 3000$).
• One line with an integer $c$, the number of initial connections ($1 \le c \le 1500$).
• $c$ lines, each with two integers $p$ and $q$: a connection that initially exists between hosts $p$ and $q$.
• One line with an integer $l$, the number of connection changes ($1 \le l \le 1500$).
• $l$ lines, each with two integers $r$ and $s$: the connection between hosts $r$ and $s$ is flipped. If it is currently present it disappears; if it is currently absent it appears.

Because of the magical environment, the only guarantee about $p$, $q$, $r$ and $s$ is that each lies in the range $1 \dots h$.

For each test case, print a single line with one integer: the number of hosts that are reachable from host $1$ but are not online — that is, hosts whose shortest path from host $1$ is longer than $10$ hops.