Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

int q;

#define MAX 200000

#define MOD 1000000007

struct edge

{

	int to,nxt;

}e[MAX << 1];

int edgenum = 0;

int lin[MAX] = {0};

void add(int a,int b)

{

	e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int dfn[MAX],low[MAX],tot = 0;

bool bridge[MAX << 1];

void tarjan(int k,int ine)

{

	dfn[k] = low[k] = ++tot;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if((i >> 1) == ine)continue;

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to,i >> 1);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] > dfn[k])

			{

				bridge[i] = bridge[i ^ 1] = true;

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	return;

}

int ins[MAX],siz[MAX];

int edcc = 0;

bool v[MAX];

void dfs(int k)

{

	ins[k] = edcc;v[k] = true;++siz[edcc];

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(!bridge[i] && !v[e[i].to])

		{

			dfs(e[i].to);

		}

	}

	return;

}

struct node

{

	int fa,c[2],v;

	long long sum;

	bool rev;

	node(){fa = c[0] = c[1] = v = 0;sum = 0;rev = false;}

}t[MAX];

void maintain(int rt)

{

	t[rt].sum = t[rt].v;

	if(t[rt].c[0] != 0)t[rt].sum = t[rt].sum * t[t[rt].c[0]].sum % MOD;

	if(t[rt].c[1] != 0)t[rt].sum = t[rt].sum * t[t[rt].c[1]].sum % MOD;

	return;

}

void pushdown(int rt)

{

	if(!t[rt].rev)return;

	t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

	swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	return;

}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int x,int y){makeroot(x);t[x].fa = y;return;}

int findroot(int k){access(k);splay(k);while(t[k].c[0] != 0)k = t[k].c[0];return k;}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	tarjan(1,-1);

	for(int i = 1;i <= n;++i)

	{

		if(!v[i])

		{

			++edcc;

			dfs(i);

		}

	}

	for(int i = 1;i <= edcc;++i)

	{

		t[i].v = siz[i] == 1 ? 1 : 2;

	}

	for(int k = 1;k <= n;++k)

	{

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ins[k] != ins[e[i].to] && findroot(ins[k]) != findroot(ins[e[i].to]))

			{

				link(ins[k],ins[e[i].to]);

			}

		}

	}

	scanf("%d",&q);

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		a = ins[a];b = ins[b];

		makeroot(a);access(b);splay(b);

		printf("%lld\n",t[b].sum);

	}

	return 0;

}