萌新刚学Tarjan0.000001s求救（玄关

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e4+5;

vector<pair<int,int>>v;

vector<int>v1[N];

int dfn[N],low[N],idx,n,m,rt,cnt=0,bel[N],bri[N];

vector<vector<int> >eDCC;

stack<int>st;

vector<int>h[N];

void add(int u,int v){
	::v.push_back({u,v});
	h[u].push_back(::v.size()-1);
}

void Tarjan(int x,int edge){
	dfn[x]=++idx;
	low[x]=idx;
	st.push(x);
	for(auto j:h[x]){
		int y=v[j].second;
		if(!dfn[y]){
			Tarjan(y,j);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				bri[j]=bri[j^1]=1;
			}
		}
		else if(j!=(edge^1)){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		cnt++;
		vector<int>c;
		while(1){
			int y=st.top();
			st.pop();
			c.push_back(y);
			bel[y]=cnt;
			if(y==x) break;
		}
		eDCC.push_back(c);
	}
} 

vector<int>e[N];

int a[N],fa[N][21];

void dfs(int x,int pre){
	for(auto i:e[x]){
		if(i==pre) continue;
		a[i]=a[x]+1;
		fa[i][0]=x;
		dfs(i,x);
	}
}

int lca(int u,int v){
	if(a[u]<a[v]) swap(u,v);
	int z=a[u]-a[v];
	for(int i=0;i<=20&&z;i++,z/=2){
		if(z&1){
			u=fa[u][i];
		}
	}
	if(u==v){
		return u;
	}
	for(int i=20;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
		v1[x].push_back(y);
		v1[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			Tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		for(auto x:v1[i]){
			if(bel[i]!=bel[x]){
				e[bel[i]].push_back(bel[x]);
				e[bel[x]].push_back(bel[i]);
			}
		}
	}
	dfs(1,-1);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			if(fa[i][j-1]){
				fa[i][j]=fa[fa[i][j-1]][j-1];
			}
		}
	}
	int tot;
	cin>>tot;
	while(tot--){
		int x,y;
		cin>>x>>y;
		x=bel[x],y=bel[y];
		int ans=a[x]+a[y]-2*a[lca(x,y)]+1;
		string s;
		while(ans){
			s.push_back(ans%2+'0');
			ans/=2;
		}
		reverse(s.begin(),s.end());
		cout<<s<<endl;
	}
	return 0;
}