Problem Description

Give an connected undirected graph with $n$ nodes and $m$ edges, ($n,m\leq 10^5$) which has no selfloops or multiple edges $initially$.
Now we have $q$ operations ($q\leq 10^5$):
  
$\cdot 1\ u\ v$: add an undirected edge from $u$ to $v$; $(u \neq v\&\& 1 \leq u,v \leq n)$
$\cdot 2\ u\ v$: count the number of $mustedges$ from $u$ to $v$; $(1 \leq u,v \leq n)$.

$mustedge$: we define set $E_i$ as a path from $u$ to $v$ which contain edges in this path, and $| \cap_1^kE_i |$ is the number of $mustedges$. $| x |$ means size of set $x$, and $E_1, E_2\dots E_k$ means all the paths.
It's guaranteed that $\sum{n},\sum{m},\sum{q}\leq 10^6$
Please note that maybe there are more than one edges between two nodes after we add edges. They are not the same, which means they can be in a set at the same time. Read the sample data for more information.

Input

Input starts with an integer $T$, denoting the number of test cases.
For each case:
First line are two number $n$ and $m$;
Then next $m$ lines, each contains two integers $u$ and $v$, which indicates an undirected edge from $u$ to $v$;
Next line contains a number $q$, the number of operations;
Then next $q$ lines, contains three integers $x$, $u$ and $v$ where $x$ is the operation type, which describes an operation.

Output

For each test case, output "Case #x:" where $x$ is the test case number starting from 1.
In each test case, print a single number one line when query the number of $mustedges$.

2
4 3
1 2
2 3
3 4
5
2 1 4
1 2 3
2 1 4
2 2 3
2 2 4
8 9
1 2
2 3
1 3
3 4
4 5
4 6
5 7
5 8
7 8
5
2 7 8
2 1 6
2 4 7
1 6 8
2 5 6

Case #1:
3
2
0
1
Case #2:
0
2
1
0