Which intersections did I pass?

Seunghyun lives in a town with $N$ intersections and $M$ two-way roads. Each road joins two different intersections, and you can travel between any two intersections along one or more roads. At most one road directly joins a given pair of intersections. For the convenience of the residents, the intersections are numbered $1$ to $N$.

On Sunday, Seunghyun left his own house and went to visit his friend Minsu, who lives in the same town. He had moved in only recently, so he knew nothing about the road network and could recognize only his own house and Minsu's house. He wandered for a long time before he reached Minsu's house, and he passed through some intersections several times on the way.

Seunghyun remembers two things. After he set out he never stopped by the intersection where his own house is again, and the moment he reached the intersection where Minsu's house is he walked straight in. So the route he walked starts at the intersection of his own house and ends at the intersection of Minsu's house, and in between it passes through neither of those two intersections. Every other intersection may be passed any number of times.

Seunghyun wants to know how many intersections lie on at least one route that agrees with this memory. The starting intersection of his own house and the final intersection of Minsu's house both count as passed. He then went one step further and wondered what that count would be if his house were at intersection $a$ and Minsu's house at intersection $b$.

Write a program that answers his questions.

The first line contains the number of test cases $T$ ($1 \le T \le 1000$).

The first line of each test case contains the number of intersections $N$ ($2 \le N \le 200000$) and the number of roads $M$ ($1 \le M \le 500000$), separated by a space. Each of the next $M$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$) separated by a space, meaning that a road directly joins intersection $u$ and intersection $v$. The next line contains the number of questions $Q$ ($1 \le Q \le 500000$). The $i$-th of the next $Q$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$) separated by a space, asking about the case where Seunghyun's house is at intersection $a_i$ and Minsu's house is at intersection $b_i$.

Over all test cases the sum of $N$ is at most $200000$, and the sum of $M$ and the sum of $Q$ are each at most $500000$.

For each test case, print $Q$ lines. The $i$-th of them contains the answer to the $i$-th question, that is, the number of intersections Seunghyun could have passed when his house is at intersection $a_i$ and Minsu's house is at intersection $b_i$. Do not print a blank line between different test cases.