本地 0.5 s，实测 TLE on #3 #4 #5 #6

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m;
int q;
struct node{
	int nex,to;
}e[500005],E[500005];
int He[500005];
int he[500005];
int tot;
int ttt;
int top;
int col[500005];
int f[200005][21];
int dep[200005];
int bridge[500005];

inline void add(int x,int y){
	e[++tot].nex=he[x];
	e[tot].to=y;
	he[x]=tot;
}

int low[200005];
int dfn[200005];
int Id;
int st[200005];
int tp;


inline void Tarjan(int x,int fa){
	low[x]=dfn[x]=++Id;
	st[++tp]=x;
	for (int i=he[x];i;i=e[i].nex){
		int v=e[i].to;
		if (!dfn[v]){
			Tarjan(v,x);
			low[x]=min(low[x],low[v]);
		}
		else if (v!=fa){
			low[x]=min(low[x],dfn[v]);
		}
	}
	if (low[x]==dfn[x]){
		int y;
		top++;
		do{
			y=st[tp];
			tp--;
			col[y]=top;
		}while (y!=x);
	}
}

inline void Add(int x,int y){
	E[++ttt].nex=He[x];
	E[ttt].to=y;
	He[x]=ttt; 
}


inline void dfs(int x,int fa){
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for (int i=1;i<=17;i++){
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for (int i=He[x];i;i=E[i].nex){
		int v=E[i].to;
		if (v!=fa){
			dfs(v,x);
		}
	}
}

inline int lca(int x,int y){
	if (dep[x]<dep[y]){
		swap(x,y);
	}
	for (int k=17;k>=0;k--){
		if (dep[f[x][k]]>=dep[y]){
			x=f[x][k];
		}
	}
	if (x==y) return x;
	for (int k=17;k>=0;k--){
		if (f[x][k]!=f[y][k]){
			x=f[x][k];
			y=f[y][k];
		}
	}
	return f[x][0];
}

signed main(){
	ios::sync_with_stdio(0);
	n=read();
	m=read();
	for (register int i=1;i<=m;i++){
		int x=read();
		int y=read();
		add(x,y);
		add(y,x);
	}
	Tarjan(1,0);
	for (register int x=1;x<=n;x++){
		for (register int i=he[x];i>1;i=e[i].nex){
			int v=e[i].to;
			if (col[v]!=col[x]){
				Add(col[x],col[v]);
				Add(col[v],col[x]);
			}
		}
	}
	dfs(1,0);
	q=read();
	while (q--){
		int a=read();
		int b=read();
		a=col[a];
		b=col[b];
		printf("%d\n",dep[a]+dep[b]-2*dep[lca(a,b)]);
	}
	
	return 0;
}