C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 8280K, 提交时间: 2018-08-07 15:47:42

#include<cstdio>
#include<vector>
const int maxn=100010,maxm=210000,maxv=210;
struct Edge{int to,cap;Edge*rev,*next;};
struct Graph{
	int n;
	Edge E[maxm],*ne,*fir[maxn];
	void init(int n){ne=E;for(int i=this->n=n;i>=0;i--)fir[i]=0;}
	void link(int a,int b,int c=1){
		*ne=(Edge){b,c,ne+1,fir[a]};fir[a]=ne++;
		*ne=(Edge){a,c,ne-1,fir[b]};fir[b]=ne++;
	}
}G1,G2,T;
int dfn[maxn],low[maxn],now,stk[maxn],top,bcc[maxn];
void cmin(int&a,int b){b<a?a=b:1;}
void dfs1(int i,int f){
	dfn[i]=low[i]=++now;
	stk[top++]=i;
	for(Edge*e=G1.fir[i];e;e=e->next){
		if(!dfn[e->to]){
			dfs1(e->to,i);
			cmin(low[i],low[e->to]);
		}
		else if(e->to!=f)cmin(low[i],dfn[e->to]);
	}
	if(low[i]==dfn[i]){
		do bcc[stk[--top]]=i;
		while(stk[top]!=i);
	}
}
int id[maxn],tot;
void dfs2(int s,int i,int f){
	if(id[i])id[s]<id[i]?G2.link(id[s],id[i]),1:1;
	else for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i]&&e->to!=f)dfs2(s,e->to,i);
}
Edge*cur[maxv];
int Q[maxv],D[maxv];
int dfs(int i,int t,int c){
	if(i==t||!c)return c;
	int fl=0,f;
	for(Edge*&e=cur[i];e&&c;e=e->next)
		if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,t,c<e->cap?c:e->cap)))
			fl+=f,e->cap-=f,e->rev->cap+=f,c-=f;
	return fl;
}
int mf(int s,int t){
	for(int f=0;;f+=dfs(s,t,1<<30)){
		for(int i=0;i<=G2.n;i++)D[i]=0,cur[i]=G2.fir[i];
		for(int*H=Q,*T=Q+(D[*Q=t]=1);H<T;H++)
			for(Edge*e=G2.fir[*H];e;e=e->next)
				if(e->rev->cap&&!D[e->to])D[*T++=e->to]=D[*H]+1;
		if(!D[s])return f;
	}
}
void solve(std::vector<int>V){
	if(V.size()<2)return;
	for(Edge*e=G2.E;e<G2.ne;e++)e->cap=1;
	T.link(V[0],V[1],mf(V[0],V[1]));
	std::vector<int>V0,V1;
	for(int i=0;i<V.size();i++)D[V[i]]?V1.push_back(V[i]):V0.push_back(V[i]);
	solve(V0);
	solve(V1);
}
int f[maxv][maxv];
void dfs_t(int s,int i,int fa,int v){
	f[s][i]=v;
	for(Edge*e=T.fir[i];e;e=e->next)
		if(e->to!=fa)dfs_t(s,e->to,i,v<e->cap?v:e->cap);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	G1.init(n);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G1.link(a,b);
	}
	dfs1(1,0);
	std::vector<int>V;
	for(int i=1;i<=n;i++){
		int d=0;
		for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i])d++;
		if(d>2)V.push_back(id[i]=++tot);
	}
	G2.init(tot);
	T.init(tot);
	for(int i=1;i<=n;i++)if(id[i])
		for(Edge*e=G1.fir[i];e;e=e->next)if(bcc[e->to]==bcc[i])dfs2(i,e->to,i);
	solve(V);
	for(int i=1;i<=tot;i++)dfs_t(i,i,i,1<<30);
	int Q;
	scanf("%d",&Q);
	while(Q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",bcc[x]!=bcc[y]?1:id[x]&&id[y]?f[id[x]][id[y]]:2);
	}
}