#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,M=5e6+5;
int head[N],tot=1;
int a[N],b[N];
struct{int to,nxt;}edge[M<<1];
void addedge(int u,int v)
{
    edge[++tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int dfn[N],low[N],id;
bool cut[N];
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++id;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                cut[i]=cut[i^1]=1;
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
bool vis[N];
int fa[N],cnt;
void dfs(int u)
{
    if(vis[u]) return;
    vis[u]=1;
    fa[u]=cnt;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(cut[i]) continue;
        dfs(v);
    }
}
int dp[N][21],dep[N],lg[N];
void DFS(int u,int f)
{
    dp[u][0]=f;
    dep[u]=dep[f]+1;
    for(int i=1;i<=20;++i)
        dp[u][i]=dp[dp[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==f)
            continue;
        DFS(v,u);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y])
        x=dp[x][lg[dep[x]-dep[y]]];
    if(x==y) return x;
    for(int k=20;k>=0;--k)
        if(dp[x][k]!=dp[y][k])
            x=dp[x][k],y=dp[y][k];
    return dp[x][0];
}
void print(int n)
{
    string s;
    while(n)
    {
        s+=n%2+'0';
        n/=2;
    }
    reverse(s.begin(),s.end());
    cout<<s;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>a[i]>>b[i];
        addedge(a[i],b[i]);
        addedge(b[i],a[i]);
    }
    lg[0]=-1;
    for(int i=1;i<=n;++i)
    {
        
        if(!dfn[i])
            tarjan(i,0);
        lg[i]=lg[i>>1]+1;
    }

    for(int i=1;i<=n;++i)
        if(!vis[i])
        {
            ++cnt;
            dfs(i);
        }
    memset(head,0,sizeof head);
    tot=0;
    for(int i=1;i<=m;++i)
    {
        int u=fa[a[i]],v=fa[b[i]];
        if(u!=v)
        {
            addedge(u,v);
            addedge(v,u);
        }
    }
    for(int i=1;i<=n;++i)
        if(!dep[i])
            DFS(i,0);
    int q;
    for(cin>>q;q--;)
    {
        int x,y;
        cin>>x>>y;  
        x=fa[x],y=fa[y];
        int LCA=lca(x,y);
        assert(LCA>0&&LCA<=n);
        print(dep[x]+dep[y]-2*dep[LCA]+1);
        cout<<'\n';
    }
}