rt，AC On #2, #7

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10100, maxm = 50500;
struct Edge {
	int to, nxt;
}edge[maxm << 1], nedge[maxm << 1];
int tot = -1, ntot = -1;
int h[maxn], nh[maxn];
void add(int u, int v) {
	edge[++tot] = (Edge){v, h[u]};
	h[u] = tot;
}
void nadd(int u, int v) {
	nedge[++ntot] = (Edge){v, nh[u]};
	nh[u] = ntot;
}
int n, m;
int q, bridge_cnt;
int dfn[maxn], low[maxn];
int timer, bcc_cnt, bccno[maxn];
int LOG[maxn];
bool in_stack[maxn];
vector<int> bcc[maxn];
stack<int> S;
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++timer;
	int child = 0;
	S.push(u);
	for (int i = h[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (dfn[v] == 0) {
			child++;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if (v != fa) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		if (fa != u) ++bridge_cnt;
		++bcc_cnt;
		while (1) {
			int x = S.top();
			S.pop();
			bccno[x] = bcc_cnt;
			bcc[bcc_cnt].push_back(x);
			if (x == u) break;
		}
	}
}
int dep[maxn], f[maxn][21];
void dfs(int u) {
	dep[u] = dep[f[u][0]] + 1;
	for (int i = nh[u]; ~i; i = nedge[i].nxt) {
		int v = nedge[i].to;
		if (v == f[u][0]) continue;
		f[v][0] = u;
		dfs(v);
	}
}
int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int K = 0;
	while ((1 << (K + 1)) <= dep[x]) ++K;
	for (int j = K; j >= 0; j--) {
		if (dep[f[x][j]] >= dep[y]) x = f[x][j];
	}
	if (x == y) return x;
	for (int j = K; j >= 0; j--) {
		if (f[x][j] != f[y][j]) x = f[x][j], y = f[y][j];
	}
	return f[x][0];
}
void init() {
	for (int i = 2; i <= n; i++) LOG[i] = LOG[i >> 1] + 1;
}
void print(int x) {
	for (int i = LOG[x]; i >= 0; i--) cout << ((x >> i) & 1);
	cout << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	memset(nh, -1, sizeof(nh));
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0) tarjan(i, i);
	}
	for (int u = 1; u <= n; u++) {
		for (int i = h[u], v; ~i; i = edge[i].nxt) {
			v = edge[i].to;
			if (bccno[u] != bccno[v]) nadd(bccno[u], bccno[v]);
		}
	}
	dfs(1);
	for (int j = 1; (1 << j) <= n; j++) {
		for (int i = 1; i <= n; i++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	init();
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		int lca = LCA(a, b);
		print(dep[a] + dep[b] - 2 * dep[lca] + 1);
	}
	return 0;
}