#include<iostream>
#include<vector>
using namespace std;
int m,n;
struct Edge
{
	int x,y;
}te;
vector<Edge> edge;
vector<int> pic[10005];
vector<int> pic2[10005];
bool cut[100005];
int dfn[10005];
int low[10005];
int order=0;
int cl=0;
int color[10005];
void Tarjan(int now,int last)
{
	order++;
	dfn[now]=order;
	low[now]=order;
	for(int i=0;i<pic[now].size();i++)
	{
		int next=edge[pic[now][i]].y;
		int ano=pic[now][i]%2;
		if(ano)//1->0
		{
			ano=pic[now][i]-1;
		}
		else//0->1
		{
			ano=pic[now][i]+1;
		}
		if(next==last)
		continue;
		if(dfn[next]==0)
		{
			Tarjan(next,now);
			low[now]=min(low[now],low[next]);
			if(low[next]>dfn[now])
			{
				cut[ano]=1;
				cut[pic[now][i]]=1;
			}
		}
		else
		{
			low[now]=min(low[now],dfn[next]);
		}
	}
}
void dfs(int now)
{
	color[now]=cl;
	for(int i=0;i<pic[now].size();i++)
	{
		int next=edge[pic[now][i]].y;
		if(cut[pic[now][i]]==0&&color[next]==0)
		{
			dfs(next);
		}
	}
}
int depth[10005];
int fa[20][10005];
void dfs2(int now,int father)
{
	depth[now]=depth[father]+1;
	fa[0][now]=father;
	for(int i=1;i<=15;i++)
	{
		fa[i][now]=fa[i-1][fa[i-1][now]];
	}
	for(int i=0;i<pic2[now].size();i++)
	{
		int next=pic2[now][i];
		if(next==father)
		continue;
		dfs2(next,now);
	}
}
int LCA(int a,int b)
{
	int ans=1;
	if(depth[b]>depth[a])
	{
		swap(a,b);
	}
	for(int i=15;i>=0;i--)
	{
		if(depth[fa[i][a]]>=depth[b])
		{
			a=fa[i][a];
			ans+=(1<<i);
//			cout<<'+'<<(1<<i)<<endl;
		}
	}
	if(a==b)
	return ans;
	for(int i=15;i>=0;i--)
	{
		if(fa[i][a]!=fa[i][b])
		{
			a=fa[i][a];
			b=fa[i][b];
			ans+=(1<<i);
			ans+=(1<<i);
//			cout<<"++"<<(1<<i)<<endl;
		}
	}
	return ans+2;
//	return fa[0][a];
}
int aaa[20];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		te.x=x;
		te.y=y;
		edge.push_back(te); 
		te.y=x;
		te.x=y;
		edge.push_back(te); 
	}
	for(int i=0;i<edge.size();i++)
	{
		pic[edge[i].x].push_back(i); 
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		{
			Tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(color[i]==0)
		{
			cl++;
			dfs(i);
		}
	}
	for(int i=0;i<edge.size();i++)
	{
		if(cut[i])
		{
			pic2[color[edge[i].x]].push_back(color[edge[i].y]);
		}
	}
	dfs2(1,0);
	int tot;
	scanf("%d",&tot);
	for(int i=1;i<=tot;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int tt=0;
		int tmp=LCA(color[x],color[y]);
		while(tmp)
		{
			tt++;
			aaa[tt]=tmp%2;
			tmp/=2;
		}
		for(int i=tt;i>=1;i--)
		{
			printf("%d",aaa[i]);
		}
		printf("\n");
	}
	return 0;
}