#include <bits/stdc++.h>
#define fi first 
#define se second
#define mp make_pair
#define lb lower_bound
#define pb push_back
#define bit(n) (1LL << (n))
#define getbit(x, i) (((x) >> (i)) & 1)
#define pii pair <int, int>
#define ALL(x) x.begin(), x.end()
using namespace std;
const int oo = 1e9;
const long long ooo = 1e18;

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int lim = 5e4 + 5;
struct disjoint_set {
    int h[lim], sz[lim];
    disjoint_set() {
        memset(h, -1, sizeof(h));
        fill(sz, sz + lim, 1);
    }
    int fh(int nd) {
        return h[nd] == -1 ? nd : h[nd] = fh(h[nd]);
    }
    bool same_par(int x, int y) {
        return fh(x) == fh(y);
    }
    bool merge(int x, int y) {
        x = fh(x), y = fh(y);
        if(x != y) {
            if(sz[x] < sz[y])
                swap(x, y);
            sz[x] += sz[y];
            h[y] = x;
        }
        return x != y;
    }
};
vector<int> edges[lim];
int disc[lim], low[lim], t;
vector<pair<int, int>> bridges;
void tarjan(int nd, int pr = -1) {
    disc[nd] = low[nd] = t++;
    for(auto x : edges[nd]) {
        if(x == pr)
            continue;
        if(disc[x] == -1) {
            tarjan(x, nd);
            low[nd] = min(low[nd], low[x]);
        }
        else {
            low[nd] = min(low[nd], disc[x]);
        }
        if(low[x] > disc[nd])   
            bridges.pb(mp(nd, x));
    }   
}
bool vis[lim];
void dfs(int nd, int origin, vector<pair<int, int>> &a) {
    vis[nd] = 1;
    a.pb(mp(nd, origin));
    for(auto i : edges[nd]) {
        if(!vis[i]) {
            dfs(i, origin, a);
        }
    }

}
int main() {
    memset(disc, -1, sizeof(disc));
    memset(low, -1, sizeof(low));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> adj;
    for(int i = 1; i <= n + 1; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].pb(v);
        edges[v].pb(u);
        adj.pb(mp(u, v));
    }
    tarjan(1);
    // cerr << "bridge cnt: " << bridges.size() << endl;
    for(auto &p : bridges) {
        if(p.fi > p.se)
            swap(p.fi, p.se);
        // cerr << p.fi << " " << p.se << endl;
    }
    sort(bridges.begin(), bridges.end());
    disjoint_set dsu;
    for(auto p : adj) {
        if(p.fi > p.se)
            swap(p.fi, p.se);
        if(!binary_search(bridges.begin(), bridges.end(), p)) {
            // not bridge
            dsu.merge(p.fi, p.se);
        }
    }
    // nbd -> non bridge degree
    int nbd[n + 1];
    memset(nbd, 0, sizeof(nbd));
    // cerr << "nbd" << endl;
    for(int i = 1; i <= n; ++i) {
        for(auto x : edges[i]) {
            if(dsu.same_par(i, x)) {
                ++nbd[i];
            }
        }
        // cerr << nbd[i] << " ";
    }
    // cerr << endl;
    for(int i = 1; i <= n; ++i)
        edges[i].clear();
    for(auto p : adj) {
        if(p.fi > p.se)
            swap(p.fi, p.se);
        if(binary_search(bridges.begin(), bridges.end(), p)) {
            // bridge
            edges[p.fi].pb(p.se);
            edges[p.se].pb(p.fi);
        }
    }
    // fi -> node to find
    // se -> last node in the important cc
    vector<vector<pair<int, int>>> v;
    bool used[n + 1];
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; ++i) {
        // cerr << dsu.fh(i) << " " << dsu.sz[dsu.fh(i)] << endl;
        if(dsu.sz[dsu.fh(i)] > 1 && !used[dsu.fh(i)]) {
            // cerr << "dfs " << i << endl;
            vector<pair<int, int>> cur;
            used[dsu.fh(i)] = 1;
            // find for every other node the original
            memset(vis, 0, sizeof(vis));
            for(int j = 1; j <= n; ++j) {
                if(dsu.fh(j) == dsu.fh(i))
                    dfs(j, j, cur);
            }
            sort(cur.begin(), cur.end());
            v.pb(cur);
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(nbd[i] == 4) {
            // special special case
            int spec = i;
            disjoint_set dsu;
            for(auto p : adj) {
                if(p.fi != i && p.se != i)
                    dsu.merge(p.fi, p.se);
            }
            while(q--) {
                int x, y;
                cin >> x >> y;
                int res = 1;
                for(auto vec : v) {
                    int ndx = (*lb(vec.begin(), vec.end(), mp(x, 0))).se, ndy = (*lb(vec.begin(), vec.end(), mp(y, 0))).se;
                    // cerr << x << " " << y << " " << ndx << " " << ndy << endl;
                    if(ndx == ndy)
                        res *= 1;
                    else if(nbd[ndx] == 4 || nbd[ndy] == 4 || dsu.same_par(x, y)) 
                        res *= 2;
                    else
                        res *= 4;
                }
                cout << res << endl;
            }
            exit(0);
        }
    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        int res = 1;
        for(auto vec : v) {
            int ndx = (*lb(vec.begin(), vec.end(), mp(x, 0))).se, ndy = (*lb(vec.begin(), vec.end(), mp(y, 0))).se;
            // cerr << ndx << " " << ndy << endl;
            if(ndx == ndy)
                res *= 1;
            else if(nbd[ndx] == 3 || nbd[ndy] == 3)
                res *= 3;
            else if(v.size() == 1)
                res *= 4;
            else
                res *= 2;
        }
        cout << res << endl;
    }
    return 0;
}