#include using namespace std; using LL=long long; using ULL=unsigned long long; #define rep(i,n) for(int i=0;i<(n);i++) struct rooted_tree{ private: int N; int logN; vector> E; int Root; vector D; vector> P; public: rooted_tree(int n){ N=n; E.resize(n); logN=0; while(1< Q; Q.push(Root); while(Q.size()){ int p=Q.front(); Q.pop(); for(int e:E[p]){ if(D[e]!=-1) continue; D[e]=D[p]+1; P[0][e]=p; Q.push(e); } } P[0][Root] = Root; rep(d,logN) rep(i,N) P[d+1][i] = P[d][P[d][i]]; } int lca(int u,int v){ if(D[u]=0; d--) if(D[u] >= D[v]+(1<=0; d--) if(P[d][u]!=P[d][v]){ u=P[d][u]; v=P[d][v]; } return P[0][u]; } int distance(int u,int v){ int g=lca(u,v); return D[u]+D[v]-D[g]*2; } }; struct graph_original{ private: int N; vector> E; vector dfsP; vector dfsD; vector condition_a; vector dfsI; private: int dfs1(int p){ dfsI.push_back(p); int backedge = dfsD[p]; for(int e:E[p]){ if(dfsD[e]!=-1){ backedge = min(backedge,dfsD[e]); continue; } dfsD[e] = dfsD[p]+1; dfsP[e] = p; int res = dfs1(e); if(res>=dfsD[p]) condition_a[e]=1; backedge = min(backedge,res); } return backedge; } public: void construct_dfsTree(int root){ dfsP.assign(N,-1); dfsD.assign(N,-1); condition_a.assign(N,0); dfsD[root] = 0; dfs1(root); } public: graph_original(int n){ N=n; E.resize(N); } void add_edge(int u,int v){ E[u].push_back(v); E[v].push_back(u); } rooted_tree construct_tree(int root){ rooted_tree res(N); construct_dfsTree(0); int p=-1; struct QueueNode { int v,p; }; queue Q; Q.push({0,-1}); while(Q.size()){ auto q = Q.front(); Q.pop(); if(q.p != -1) res.add_edge(q.p,q.v); for(int e:E[q.v]){ if(dfsD[e] != dfsD[q.v]+1) continue; QueueNode nx = {e,q.p}; if(condition_a[e]){ nx.p = res.add_node(); res.add_edge(q.v,nx.p); } Q.push(nx); } } res.init_for_lca(root); return res; } }; int main(){ int N,M; scanf("%d%d",&N,&M); graph_original G(N); rep(i,M){ int u,v; scanf("%d%d",&u,&v); u--; v--; G.add_edge(u,v); } rooted_tree T = G.construct_tree(0); int Q; cin>>Q; rep(i,Q){ int x,y; scanf("%d%d",&x,&y); x--; y--; int Dxy = T.distance(x,y); printf("%d\n",max(0,Dxy/2-1)); } return 0; }