hdu3686

/*
无向图边的双连通分量，在同一个连通分量里的边之间的路径不会有必须经过的点
点和边的下标从1开始。
*/
#include <cstdio>
#include <vector>
using namespace std;
const int N=10005; //点数
const int M=100005; //边数,边的双连通分量的点数是O(M)
const int QN=10005;
const int NUM=N+M; //双连通分量的点数
typedef pair<int, int> pii;
#define mkpii make_pair<int, int>

struct e{
	int v;
	e* nxt;
}es[M<<1], *fir[NUM];
int n, m, en, scnt;//scnt是连通分量的个数
int tes[M][2];
vector<int> has[N]; //每个点相关的 连通分量
int stk[N], minc[N], dep[NUM], vid[N], eid[M];
bool vis[NUM];
int top;
pii qs[QN];
vector<pii> qlca[NUM];
e estk[NUM];  //用于模拟dfs的数据结构
int par[NUM], fa[NUM], anc[QN]; //par[i]为i的直接前驱, fa用于并查集, anc[i]为第i次查询的结果


void add_e(int u, int v){
	es[en].v=v;
	es[en].nxt=fir[u];
	fir[u]=&es[en++];
}
void insert(int u, int v){
	add_e(u, v);
	add_e(v, u);
}
void dfs(int u, int f, int d){
	vis[u]=true;
	minc[u]=dep[u]=d;
	stk[++top]=u;
	e* cur;
	int v;
	for(cur=fir[u]; cur; cur=cur->nxt){
		if(!vis[v=cur->v]){
			dfs(v, u, d+1);
			if(minc[u]>minc[v]){
				minc[u]=minc[v];
			}
			if(minc[v]>dep[u]){ //边u-->v作为一个连通分量
				has[v].push_back(++scnt);
				has[u].push_back(scnt);
				--top;
			}else if(minc[v]==dep[u]){
				++scnt;
				do{
					has[stk[top--]].push_back(scnt);
				}while(stk[top]!=u);
				has[u].push_back(scnt);
			}
		}else if(v!=f){
			if(minc[u]>minc[v]){
				minc[u]=minc[v];
			}
		}
	}
}
void edgeSCC(){
	int i;
	for(i=1; i<=n; i++){
		has[i].clear();
		vis[i]=false;
	}
	for(top=-1, scnt=0, i=1; i<=n; i++){
		if(vis[i]) continue;
		dfs(i, -1, 1);
	}
}
//构建新树
void reBuild(){
	int i, s, j;
	for(en=0, i=1; i<=scnt; i++){
		fir[i]=NULL;
	}
	for(i=1; i<=n; i++){
		s=has[i].size();
		if(s==1){
			vid[i]=has[i][0];
		}else if(s>1){
			vid[i]=++scnt;
			fir[scnt]=NULL;
			for(j=0; j<s; j++){
				insert(scnt, has[i][j]);
			}
		}else{
			vid[i]=0;
		}
	}
	int su, sv, u, v, iu, iv;
	bool flag;
	//给每一条边编号
	for(i=1; i<=m; i++){
		u=tes[i][0];
		v=tes[i][1];
		for(flag=true, su=has[u].size(), iu=0; iu<su&&flag; iu++){
			for(sv=has[v].size(), iv=0; iv<sv&&flag; iv++){
				if(has[u][iu]==has[v][iv]){
					flag=false;
					eid[i]=has[u][iu];
					break;
				}
			}
		}
	}
}

//向栈里添加节点u
void push(int u, int p, int& top){
	top++;
	estk[top].v = u;
	estk[top].nxt = fir[u];
	par[u] = p;
	fa[u] = u;
	vis[u] = true;
}
int findFa(int u){
	int k = u;
	while(k != fa[k]) k = fa[k];
	while(u != k){
		int tf = fa[u];
		fa[u] = k;
		u = tf;
	}
	return k;
}
//qn为查询lca的次数，qs记录查询lca的两个几点，anc记录每次查询的结果
void lca(pii* qs, int qn, int* anc, int n){
	int i, r, u, v, top;
	for(i = 1; i <= n; i++){
		qlca[i].clear();
		vis[i] = false;
	}
	for(i = 1; i <= qn; i++){
		//这里的pii的first表示第几个查询,second表示另一个点
		qlca[qs[i].first].push_back(mkpii(i, qs[i].second));
		qlca[qs[i].second].push_back(mkpii(i, qs[i].first));
		if(qs[i].first == qs[i].second){
			anc[i] = qs[i].first;
		}
	}
	for(i=1; i<= n; i++){
		if(vis[i]) continue;
		r = i;
		top = -1;
		push(r, -1, top);
		dep[r]=1;
		while(top >= 0){
			u = estk[top].v;
			if(!estk[top].nxt){ //u为根的子树已经访问完毕
				if(par[u] >= 0){
					fa[u] = par[u];
				}
				top--;
				continue;
			}
			v = estk[top].nxt->v;
			estk[top].nxt = estk[top].nxt->nxt;
			if(v != par[u]){
				push(v, u, top);
				dep[v]=dep[u]+1;
				//处理查询
				int size = qlca[v].size();
				for(i = 0; i < size; i++){
					int k = qlca[v][i].second;
					if(v != k && vis[k]){ //要求另一个点已经被访问了
						anc[qlca[v][i].first] = findFa(k);
					}
				}
			}
		}
	}
}

bool input(){
	scanf("%d%d", &n, &m);
	if(n==0) return false;
	int i;
	for(en=0, i=1; i<=n; i++){
		fir[i]=NULL;
	}
	for(i=1; i<=m; i++){
		scanf("%d%d", tes[i], tes[i]+1);
		insert(tes[i][0], tes[i][1]);
	}
	return true;
}
void solve(){
	edgeSCC();
	reBuild();
	int i, qn, d;
	scanf("%d", &qn);
	for(i=1; i<=qn; i++){
		scanf("%d%d", &qs[i].first, &qs[i].second);
		qs[i].first=eid[qs[i].first];
		qs[i].second=eid[qs[i].second];
	}
	lca(qs, qn, anc, scnt);
	for(i=1; i<= qn; i++){
		d=dep[qs[i].first]+dep[qs[i].second]-dep[anc[i]]*2;
		printf("%d\n", d>>1);
	}
}
int main(){
	while(input()) solve();
	return 0;
}