#include<bits/stdc++.h>
#define int long long
using namespace std;
int rd() {int x=0,f=1;char c=getchar();while(!isdigit(c))f=(c=='-'?-1:f),c=getchar();while(isdigit(c))x=x*10+c-'0',c=getchar();return x*f;}
const int N=200005;
int n,m,q,seed;
struct node {int nd,dis,fr,pos;};
bool operator<(node a,node b) {return a.dis>b.dis;}
vector<node> G[N],R[N];
vector<int> alls,allt;
int vis[N],dis[N];
priority_queue<node> qs,qt;
void generate_edges(int n, int m, unsigned seed) {
    mt19937 gen(seed);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
    for(int i=1;i<=m;i++) {
        int u = sample();
        int v = sample();
        int w = gen();
        G[u].push_back({v,w,0,0});
        R[v].push_back({u,w,0,0});
    } // u 到 v 存在边权为 w 的边
}
signed main() {
    n=rd(),m=rd(),q=rd(),seed=rd();
    generate_edges(n,m,seed);
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end()),reverse(G[i].begin(),G[i].end());
    for(int i=1;i<=n;i++) sort(R[i].begin(),R[i].end()),reverse(R[i].begin(),R[i].end());
    memset(dis,-1,sizeof(dis));
    while(q--) {
        int s=rd(),t=rd(),meet=-1,diss=-1,dist=-1,ans=0x3f3f3f3f3f3f3f3f;
        qs.push({s,0,0,0}),qt.push({t,0,0,0});
        while(!qs.empty()||!qt.empty()) {
            if(!qs.empty()) {
                int u=qs.top().nd,fr=qs.top().fr,pos=qs.top().pos,d=qs.top().dis;qs.pop();
                if(vis[u]==2) {
                    vis[u]=3;
                    alls.push_back(u);
                    meet=u;
                    diss=d,dist=dis[u];
                    ans=diss+dist;
                    break;
                }
                if(dis[u]!=-1) continue;
                alls.push_back(u);
                vis[u]=1;
                dis[u]=d;
                if(fr&&pos<G[fr].size()-1) qs.push({G[fr][pos+1].nd,dis[fr]+G[fr][pos+1].dis});
                if(!G[u].empty()) qs.push({G[u][0].nd,dis[u]+G[u][0].dis,u,0});
            }
            if(!qt.empty()) {
                int u=qt.top().nd,fr=qt.top().fr,pos=qt.top().pos,d=qt.top().dis;qt.pop();
                if(vis[u]==1) {
                    vis[u]=3;
                    allt.push_back(u);
                    meet=u;
                    diss=dis[u],dist=d;
                    ans=diss+dist;
                    break;
                }
                if(dis[u]!=-1) continue;
                allt.push_back(u);
                vis[u]=2;
                dis[u]=d;
                if(fr&&pos<R[fr].size()-1) qt.push({R[fr][pos+1].nd,dis[fr]+R[fr][pos+1].dis});
                if(!R[u].empty()) qt.push({R[u][0].nd,dis[u]+R[u][0].dis,u,0});
            }
        }
        if(meet==-1) {
            puts("-1");
            for(int u:alls) dis[u]=-1,vis[u]=0;
            for(int u:allt) dis[u]=-1,vis[u]=0;
            alls.clear(),allt.clear(),qs=qt=priority_queue<node>();
            continue;
        }
        // printf("dis: %d -> ",s);
        // for(int u:alls) if(u!=meet) printf("(%lld,%lld) ",u,dis[u]);puts("");
        // printf("dis: %d -> ",t);
        // for(int u:allt) if(u!=meet) printf("(%lld,%lld) ",u,dis[u]);puts("");
        // printf("meet=%lld diss=%lld dist=%lld\n",meet,diss,dist);
        for(int u:alls) for(auto t:G[u]) if((vis[t.nd]&2)&&t.dis<=2*(diss-dis[u])) ans=min(ans,(u==meet?diss:dis[u])+t.dis+(t.nd==meet?dist:dis[t.nd]));
        for(int u:allt) for(auto t:R[u]) if((vis[t.nd]&1)&&t.dis<=2*(dist-dis[u])) ans=min(ans,(u==meet?dist:dis[u])+t.dis+(t.nd==meet?diss:dis[t.nd]));
        printf("%lld\n",ans);
        for(int u:alls) dis[u]=-1,vis[u]=0;
        for(int u:allt) dis[u]=-1,vis[u]=0;
        alls.clear(),allt.clear(),qs=qt=priority_queue<node>();
    }
    return 0;
}