#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
//树剖求lca+dfs序部分 
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int in[maxn],out[maxn],top[maxn];
int t,n,m,q,step;
vector<int>e[maxn];
vector<pair<int,int> >edges;
void init1(){
	for(int i=0;i<=n;i++) e[i].clear();
	edges.clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(in,0),mm(out,0),mm(top,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
    out[x]=step;
} 
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
//并查集部分
int p[maxn];
void init2(){
	for(int i=0;i<=n;i++) p[i]=i;
}
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int u,int v){
	int x=find(u);
	int y=find(v);
	if(x!=y) p[x]=y;
}
bool same(int u,int v){
	return find(u)==find(v);
}
//树状数组部分:区间更新单点查询
int tree[maxn<<2];
void change(int x,int val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
int sum(int x){
	int res=0;
    while(x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
//并查集暴力修改
void addedge(int u,int v){
	int f=lca(u,v);
	while(find(u)!=find(f)){
		change(in[find(u)],1);
		change(out[find(u)]+1,-1);
		merge(find(u),fa[find(u)]);
	}
	while(find(v)!=find(f)){
		change(in[find(v)],1);
		change(out[find(v)]+1,-1);
		merge(find(v),fa[find(v)]);
	}
} 
int Case=1;
int main(){
	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		printf("Case #%d:\n",Case++);
		scanf("%d%d",&n,&m);
		init1(),init2();
		mm(tree,0);
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			if(same(u,v)) edges.push_back(make_pair(u,v));
			else{
				e[u].push_back(v),e[v].push_back(u);
				merge(u,v);
			}
		}
		init2();
		dfs1(1,0,0);
		dfs2(1,1);
		for(auto p:edges) addedge(p.first,p.second);
		scanf("%d",&q);
		while(q--){
			int op,x,y;
			scanf("%d%d%d",&op,&x,&y);
			if(op==1) addedge(x,y);
			else{
				int f=lca(x,y);
				int ans=dep[x]+dep[y]-2*dep[f]-(sum(in[x])+sum(in[y])-2*sum(in[f]));
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}