rt

#include<bits/stdc++.h>
using namespace std;
char user;
template <typename T> inline void read(T &x){
    char ch = getchar(); T f = 1; x = 0;
    for(; (!isdigit(ch)) and ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; isdigit(ch); x = (x << 3) + (x << 1) + ch - 48, ch = getchar());
    x *= f;
}
template<typename T, typename ...Arg>void read(T &x, Arg& ...arg){
    read(x);
    read(arg...);
}
                                               
template <typename T>void write(T x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');    
}
                                                                  
template <typename T, typename ...Arg> void write(T x, Arg ...arg){
    write(x);
    putchar(user);
    write(arg...);
}
const int N = 1e5 + 5;
const int M = 2e4 + 5;
set< pair<int, int> > use;
//---------------------------------------------------------------
    int head[N], number, low[N], dfn[N], tot, cnt, color[N], dep[N], fa[N][17];
    bool vis[N];
    struct node{
        int from, to, next;
    }k[N << 1];                  
    void add(int x, int y){
        k[++number].next = head[x];
        k[number].to = y;
        k[number].from = x;
        head[x] = number;
    }   
    stack<int> q;
    void tarjan(int x, int last){
        low[x] = dfn[x] = ++tot; q.push(x); vis[x] = true;
        for(int i = head[x]; i; i = k[i].next){
            if(i == (last ^ 1) or i == last) continue;
            int to = k[i].to; 
            if(dfn[to] == 0) {
                tarjan(to, i);
                low[x] = min(low[x], low[to]);
            }
            else if(vis[to] == true) low[x] = min(low[x], dfn[to]);
        }
        if(dfn[x] == low[x]){
            int now;
            ++cnt; //cout << cnt << " : ";
            while(now != x){
                now = q.top(); q.pop();
                color[now] = cnt; //cout << now << " ";
                vis[now] = false;
            }
           // puts(" ");
        }
    }
    vector<int>v[N];
    bool cmp(node x, node y){ return color[x.from] == color[y.from] ? color[x.to] < color[y.to] : color[x.from] < color[y.from]; }
    void dfs(int x, int father){
        dep[x] = dep[father] + 1;
        fa[x][0] = father;
        for(int i = 1; i <= 15; i++)
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        for(int i = 0; i < v[x].size(); i++){
            int to = v[x][i]; if(to == father) continue;
            dfs(to, x);
        }
    }    

    int ask(int x, int y){
        //int ans = 0;
        if(dep[x] < dep[y]) swap(x, y);
        for(int i = 15; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]/*, cout << "OK" << i << "\n"*/;
        if(x == y) return x;
        for(int i = 15; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
        return fa[x][0];
    }
    stack<int>s;
    void work(int x){
        while(!s.empty()) s.pop();
        for(int i = 0; i <= 15; i++){
            if(x & (1 << i)) s.push(1);
            else s.push(0);
        }
        while(s.top() == 0) { s.pop(); }
        while(!s.empty()){
            write(s.top());
            s.pop();
        }
        puts("");
    }
//---------------------------------------------------------------
signed main(signed agrc, char const *argv[]){
    clock_t cl = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
//---------------------------------------------------------------
    int n, m; read(n, m); number = 1;
    
    for(int i = 1; i <= m; i++){
        int x, y; read(x, y);
        if(x != y and !use.count(make_pair(x, y))) {
        	add(x, y), add(y, x);
        	use.emplace(x, y); use.emplace(y, x);
		}
    }
    
    //cerr << "Time Used: " << clock() - cl << "ms" << endl;
    for(int i = 1; i <= n; i++) if(dfn[i] == 0) tarjan(i, 0);
    sort(k + 2, k + number + 1, cmp);
    if(color[k[2].from] != color[k[2].to]) v[color[k[2].from]].push_back(color[k[2].to]);
    for(int i = 3; i <= number; i++){
        if(color[k[i].from] == color[k[i - 1].from] and color[k[i].to] == color[k[i - 1].to]) continue;
            v[color[k[i].from]].push_back(color[k[i].to]);
            //v[color[k[i].to]].push_back(color[k[i].from]);
    }//cout << "qq";
    
    n = cnt; int q; read(q);	
    dfs(1, 0);
   /*for(int i = 1; i <= n; i++, puts("")){
        printf("%d :", i); for(int j = 0; j < 4; j++){
            printf("%d ", fa[i][j]);
        }
    }*/
    //cout << "sb"; return 0;
    while(q--){
        int x, y; read(x, y);
        int ans = ask(color[x], color[y]);
        ans = dep[color[x]] + dep[color[y]] - 2 * dep[ans] + 1;
        work(ans);
    }
    
//---------------------------------------------------------------
end:
    cerr << "Time Used: " << clock() - cl << "ms" << endl;
    return 0;
}

评测记录