#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;
const int P = 1000000007;

int N, M, Q, Ty;
int elast[MAX_N], ey[MAX_N << 1], enext[MAX_N << 1];
int gr[MAX_N], gsz[MAX_N], gmd[MAX_N];
vector<int> gc[MAX_N];
int dis[MAX_N], dis2[MAX_N];
map<pair<int,int>,int> ans;

void dfs(int u, int fa) {
    for (int j = elast[u], v; j; j = enext[j]) {
        if ((v = ey[j]) != fa) {
            dis2[v] = dis2[u] + 1;
            dfs(v, u);
        }
    }
}

void init(int st) {
    static int q[MAX_N], qh, qt;
    gr[st] = st;
    qh = 0, qt = 1, q[0] = st;
    while (qh != qt) {
        int u = q[qh ++];
        for (int j = elast[u], v; j; j = enext[j]) {
            if (!gr[v = ey[j]]) {
                dis[v] = dis[u] + 1;
                gr[v] = st;
                q[qt ++] = v;
            }
        }
    }
    int A = q[qt - 1];
    for (int i = 0; i < qt; i ++) {
        gr[q[i]] = 0;
        dis[q[i]] = 0;
    }
    gr[A] = st;
    qh = 0, qt = 1, q[0] = A;
    while (qh != qt) {
        int u = q[qh ++];
        for (int j = elast[u], v; j; j = enext[j]) {
            if (!gr[v = ey[j]]) {
                dis[v] = dis[u] + 1;
                gr[v] = st;
                q[qt ++] = v;
            }
        }
    }
    int B = q[qt - 1];
    gsz[st] = qt;
    gmd[st] = dis[B];
    gc[st].resize(dis[B] + 1, 0);
    dfs(B, 0);
    for (int i = 0; i < qt; i ++) {
        int u = q[i];
        int d = max(dis[u], dis2[u]);
        gc[st][d] ++;
    }
    // printf("st=%d, c=", st);
    // for (int d = 0; d <= gmd[st]; d ++) {
    //     printf("%d,", gc[st][d]);
    // }
    // printf("\n");
}

int power_mod(int a, int b) {
    int c = 1;
    for (; b; b >>= 1) {
        if (b & 1) c = 1ll * c * a % P;
        a = 1ll * a * a % P;
    }
    return c;
}

int main() {
    scanf("%d%d%d%d", &N, &M, &Q, &Ty);
    for (int i = 1, j = 1; i <= M; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        ey[j] = y, enext[j] = elast[x], elast[x] = j ++;
        ey[j] = x, enext[j] = elast[y], elast[y] = j ++;
    }
    for (int i = 1; i <= N; i ++) {
        if (!gr[i]) init(i);
    }
    for (int i = 1; i <= Q; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (gr[x] == gr[y]) {
            printf("-1\n");
        } else {
            x = gr[x], y = gr[y];
            if (gmd[x] < gmd[y]) swap(x, y);
            if (ans.count(make_pair(x, y))) {
                printf("%d\n", ans[make_pair(x, y)]);
            } else {
                int Dx = gmd[x], Dy = gmd[y];
                auto &cx = gc[x], &cy = gc[y];
                int res = 0;
                for (int d = Dx + 1; d <= Dx + Dy; d ++) {
                    long long t = 0;
                    for (int d2 = 0; d2 <= d && d2 <= Dy; d2 ++) {
                        if (d - d2 <= Dx) {
                            t += 1ll * cx[d - d2] * cy[d2];
                        }
                    }
                    res = (res + t % P * (d - Dx)) % P;
                }
                int res_ = power_mod(1ll * gsz[x] * gsz[y] % P, P - 2);
                res = 1ll * res * res_ % P;
                res += Dx + 1;
                printf("%d\n", res);
                ans[make_pair(x, y)] = res;
            }
        }
    }
    return 0;
}