36求条

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define sz(x) ((int)x.size())
#define inf (1 << 30)
#define pb push_back
typedef pair<int, int> PII;
const int N = 1e4 + 7;
const int P = 998244353;
int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!(ch >= '0' && ch <= '9')) {if (ch == '-') f = -f;ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
	return x * f;
}
/*
思路：边双缩点，求lca
*/
int n, m;
int dfn[N], low[N], times, bcc;
int stk[N], top, bel[N];
int dep[N], dp[N][21];
vector <int> edges[N], G[N];
void add_edges(int x, int y) {
	edges[x].pb(y);
	edges[y].pb(x);
}
void insert(int x, int y) {
	G[x].pb(y);
}
inline void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++times;
	stk[++top] = u;
	bool mark = false;
	for (auto v : edges[u]) {
		if (v == fa && !mark) mark = 1;
		else if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}else {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		bcc++;
		while (1) {
			int v = stk[top--];
			bel[v] = bcc;
			if (v == u) break;
		}
	}
}
void dfs(int u, int fa) {
	for (auto v : G[u]) {
		if (v == fa) continue;
		dep[v] = dep[u] + 1;
		dp[v][0] = u;
		dfs(v, u);
	}
}
void pre_init() {
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i); // tarjan
	for (int i = 1; i <= n; i++) {
		for (auto v : edges[i]) {
			if (bel[i] != bel[v]) {
				insert(bel[v], bel[i]);
			}
		}
	}
	dfs(1, 1);
	for (int j = 1; j <= 19; j++) {
		for (int i = 1; i <= bcc; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}
}
int get_lca(int x, int y){
	if (dep[x] < dep[y]) swap(x,y);
	int d = dep[x] - dep[y];
	for(int i = 0; d; i++, d >>= 1){
		if (d & 1) {
			x = dp[x][i];
		}
	}
	if (x != y) {
		for (int i = 19; i >= 0; i--){
			if (dp[x][i] != dp[y][i]) {
				x = dp[x][i];
				y = dp[y][i];
			}
		}
		x = dp[x][0];	
	}
	return x;
}
void two(int x) {
	vector<int> ve;
	while (x) {
		ve.pb(x % 2);
		x /= 2;
	}
	reverse(ve.begin(), ve.end());
	for (auto v : ve)
		printf("%d", v);
	putchar('\n');
}
int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read();
		add_edges(x, y);
	}
	// do sth on there
	pre_init();
	// for (int i = 1; i <= n; i++) printf("%d\n", dep[i]);
	int q = read();
	while (q--) {
		int x = read(), y = read();
		two(dep[x] + dep[y] - 2 * dep[get_lca(x, y)] + 1);
	}
	return 0;
}