#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,M=1e5+5;
vector<pair<int,int> >vec;
int head[N],tot=1;
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 n,m;
int dfn[N],low[N],id;
int cut[M<<1];
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]);
    }
}

int fa[N],cnt,vis[N];
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])
            dfs(v);
    }
}

void build(int total)
{
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i,0);
    for(int i=1;i<=n;++i)
        if(!vis[i])
        {
            ++cnt;
            dfs(i);
        }
    memset(head,0,sizeof head);
    tot=0;
    for(int i=0;i<total;++i)
    {
        int u=fa[vec[i].first],v=fa[vec[i].second];
        if(u!=v)
        {
            addedge(u,v);
            addedge(v,u);
        }
    }
}
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 u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u]>dep[v])
        u=dp[u][lg[dep[u]-dep[v]]];
    if(u==v)return u;
    for(int i=20;i>=0;--i)
        if(dp[u][i]!=dp[v][i])
            u=dp[u][i],v=dp[v][i];
    return dp[u][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);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        vec.emplace_back(u,v);
    }
    sort(vec.begin(),vec.end());
    int total=unique(vec.begin(),vec.end())-vec.begin();
    for(int i=0;i<total;++i)
    {
        int u=vec[i].first,v=vec[i].second;
        addedge(u,v);
        addedge(v,u);
    }
    build(total);
    lg[0]=-1;
    for(int i=1;i<=n;++i)
        lg[i]=lg[i>>1]+1;
    for(int i=1;i<=cnt;++i)
        if(!dep[i])
            DFS(i,0);
    int q;
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        int lca=LCA(u,v);
        if(!lca)
        {
            cout<<"1\n";
            continue;
        }
        print(dep[u]+dep[v]-2*dep[lca]+1);
        cout<<'\n';
    }
}