#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m,k;
unsigned seed;
struct edge_t{
	int v; ll w;
	friend bool operator<(const edge_t& ls,const edge_t& rs){ return ls.w<rs.w; }
};
struct node{
	ll d;
	int u,i; // the i-th edge of u
	friend bool operator<(const node& ls,const node& rs){ return ls.d>rs.d; }
};
vector<edge_t> g[N],gr[N];
void init_graph(){
	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();
		ll w = gen();
		g[u].push_back({v,w});
		gr[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++) {
		sort(g[i].begin(),g[i].end());
		sort(gr[i].begin(),gr[i].end());
	}
}
ll ds[N],dt[N];
bool vs[N],vt[N];
ll query(int s,int t){
	if(s==t) return 0;
	if(!g[s].size()||!gr[t].size()) return -1;
	// puts("here");
	vector<int> us{s},ut{t};
	priority_queue<node> qs,qt;
	ds[s]=0; vs[s]=1; qs.push({g[s][0].w,s,0});
	dt[t]=0; vt[t]=1; qt.push({gr[t][0].w,t,0});
	int mid=-1;
	while(!qs.empty()&&!qt.empty()){
		if(qs.size()<=qt.size()){
			auto [d,u,i]=qs.top(); qs.pop();
			int v=g[u][i].v;
			for(int j=i+1;j<g[u].size();++j) if(!vs[g[u][j].v]) {
				qs.push({ds[u]+g[u][j].w,u,j}); break;
			}
			if(vs[v]) continue;
			// printf("ds %d = %lld\n",v,d);
			vs[v]=true; ds[v]=d; us.push_back(v);
			if(vt[v]){ mid=v; break; }
			if(g[v].size()) qs.push({d+g[v][0].w,v,0});
		}else{
			auto [d,u,i]=qt.top(); qt.pop();
			int v=gr[u][i].v;
			for(int j=i+1;j<gr[u].size();++j) if(!vt[gr[u][j].v]) {
				qt.push({ds[u]+gr[u][j].w,u,j}); break;
			}
			if(vt[v]) continue;
			// printf("dt %d = %lld\n",v,d);
			vt[v]=true; dt[v]=d; ut.push_back(v);
			if(vs[v]){ mid=v; break; }
			if(gr[v].size()) qt.push({d+gr[v][0].w,v,0});
		}
	}
	if(mid==-1){
		for(int i:us) vs[i]=false;
		for(int i:ut) vt[i]=false;
		return -1;
	}
	ll ans=ds[mid]+dt[mid];
	for(int u:us){
		ll lim=(ds[mid]-ds[u])<<1;
		for(auto e:g[u]){
			if(e.w>=lim) break;
			if(vt[e.v]) ans=min(ans,ds[u]+e.w+dt[e.v]);
		}
	}
	for(int u:ut) {
		ll lim=(dt[mid]-dt[u])<<1;
		for(auto e:gr[u]){
			if(e.w>=lim) break;
			if(vs[e.v]) ans=min(ans,ds[e.v]+e.w+dt[u]);
		}
	}
	for(int u:us) vs[u]=false;
	for(int u:ut) vt[u]=false;
	return ans;
}
signed main(){
	scanf("%d%d%d%u",&n,&m,&k,&seed);
	init_graph();
	while(k--){
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%lld\n",query(s,t));
	}
}