Subtast #4 WA*4

#include<bits/stdc++.h>
#define int long long
#define debug(x) cout<<#x<<':'<<x<<endl
using namespace std;
namespace Fread {
const int SIZE = 16;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
}
namespace Fwrite {
const int SIZE = 65536;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
    #define getchar Fread :: getchar
    #define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = (x * 10 + (c - '0'));
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        while (c != '\n' && c != ' ') {
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
const int N=1e6+5;
int tot,to[N<<1],nxt[N<<1],head[N],ctot,col[N],sum[N];
int st[N],tp,cnt,dfn[N],low[N];
int n,m,ans,q;
vector<int> G[N];
int top[N],son[N],dep[N],siz[N],fa[N],id[N],a[N],num[N],idx;



//------------------------------------------树剖-------------------------------------------
void dfs1(int x,int f){
	siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
	int mx=INT_MIN;
  	for(int i=0;i<G[x].size();i++){
  		int y=G[x][i];
  		if(y==f) continue;
  		dfs1(y,x);
  		siz[x]+=siz[y];
  		if(siz[y]>mx)mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int hd){
	top[x]=hd;
	id[x]=++idx;
	a[idx]=num[x];
	if(son[x]) dfs2(son[x],hd);
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y!=son[x]&&y!=fa[x]) dfs2(y,y);
	}
}
struct TREE{
	int l,r,sum;
}tree[N<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
void push_up(int p){
	tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
}
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	if(l==r){
		tree[p].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
int query(int p,int l,int r){
	if(l<=tree[p].l&&tree[p].r<=r){
		return tree[p].sum;
	}
	int mid=(tree[p].l+tree[p].r)>>1,res=0;
	if(l<=mid) res+=query(ls(p),l,r);
	if(r>mid) res+=query(rs(p),l,r);
	return res;
}
int ask(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res+=query(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res+=query(1,id[x],id[y]);
	return res;
}
//------------------------------------------树剖-------------------------------------------



//-----------------------------------------Tarjian-----------------------------------------
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void tarjian(int u){
	st[++tp]=u,dfn[u]=low[u]=++cnt;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
            tarjian(v);
            low[u]=min(low[u],low[v]);
            if(low[v]==dfn[u]){
				num[++ctot]=0;
				for(int x=0;x!=v;tp--){
					x=st[tp];
					G[ctot].push_back(x);
					G[x].push_back(ctot);
				}
				G[ctot].push_back(u);
				G[u].push_back(ctot);
			}
        }
        else low[u]=min(low[u],dfn[v]);
	}
}
//-----------------------------------------Tarjian-----------------------------------------
signed main(){
	cin>>n>>m;ctot=n;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x); 
	}
	for(int i=1;i<=n;i++) num[i]=1;
	if(m!=n-1)tarjian(1);
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,ctot);
	
	cin>>q;
	for(int i=1,u,v;i<=q;i++){
		cin>>u>>v;
		cout<<ask(u,v)<<endl;
	}
	return 0;
}