#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
signed n,m,q;unsigned seed;
struct Edge{int v,w;};
vector<Edge> g1[200009],g2[200009];
struct Node{
	int d,u,id;
	friend bool operator<(const Node x,const Node y){return x.d>y.d;}
};priority_queue<Node> q1,q2;
int d1[200009],d2[200009];
bool v1[200009],v2[200009];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q>>seed;
	std::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();
        g1[u].push_back({v,w});
        g2[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++){
    	sort(g1[i].begin(),g1[i].end(),[&](Edge x,Edge y){return x.w<y.w;});
    	sort(g2[i].begin(),g2[i].end(),[&](Edge x,Edge y){return x.w<y.w;});
	}
	while(q--){
		int s,t,p=0;cin>>s>>t;
		if(s==t){cout<<0<<endl;continue;}
		if(g1[s].empty()||g2[t].empty()){cout<<-1<<endl;continue;}
		vector<int> del1,del2;del1.clear();del2.clear();del1.push_back(s);del2.push_back(t);
		d1[s]=d2[t]=0;v1[s]=v2[t]=0;
		while(!q1.empty())q1.pop();while(!q2.empty())q2.pop();
		q1.push({g1[s][0].w,s,0});q2.push({g2[t][0].w,t,0});
		while(!q1.empty()&&!q2.empty()){
			if((int)q1.size()<(int)q2.size()){
				int x=q1.top().d,u=q1.top().u,id=q1.top().id,v=g1[u][id].v;q1.pop();
				if(id+1<(int)g1[u].size())q1.push({d1[u]+g1[u][id+1].w,u,id+1});
				if(v1[v])continue;
				v1[v]=1;d1[v]=x;del1.push_back(v);
				if(v2[v]){p=v;break;}
				if(!g1[v].empty())q1.push({x+g1[v][0].w,v,0});
			}else{
				int x=q2.top().d,u=q2.top().u,id=q2.top().id,v=g2[u][id].v;q2.pop();
				if(id+1<(int)g2[u].size())q2.push({d2[u]+g2[u][id+1].w,u,id+1});
				if(v2[v])continue;
				v2[v]=1;d2[v]=x;del2.push_back(v);
				if(v1[v]){p=v;break;}
				if(!g2[v].empty())q2.push({x+g2[v][0].w,v,0});
			}
		}
		if(!p){for(int u:del1)v1[u]=0;for(int u:del2)v2[u]=0;cout<<-1<<endl;continue;}
		int ans=d1[p]+d2[p];
		for(int u:del1)for(auto f:g1[u]){
			if(f.w>=(max(d1[p],d2[p])-d1[u])*2)continue;
			if(v2[f.v])ans=min(ans,d1[u]+f.w+d2[f.v]);
		}
		for(int u:del2)for(auto f:g2[u]){
			if(f.w>=(max(d1[p],d2[p])-d2[u])*2)continue;
			if(v1[f.v])ans=min(ans,d1[f.v]+f.w+d2[u]);
		}
		for(int u:del1)v1[u]=0;for(int u:del2)v2[u]=0;cout<<ans<<endl;
	}
	return 0;
}