#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ui unsigned
#define ll long long
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define FOR(i,a,b) for(int i=(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i=(a);i>=(int)(b);--i)
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~(i);(i)=(g)[(i)].nxt,(y)=(g)[(i)].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10;
bool vis[2][N];
int n,m,Q;
ui Seed;
ll dis[2][N];
struct edge {
	int v;
	ui w;
	edge(int v,ui w):v(v),w(w) {}
	friend bool operator <(edge a,edge b) {
		return a.w<b.w;
	}
};
vector<edge> g[2][N];
struct node {
	int u,i;
	ll d;
	friend bool operator <(node a,node b) {
		return a.d>b.d;
	}
};
int Relax(bool *vis,bool *vis0,ll *dis,vector<int> &vec,vector<edge> *g,priority_queue<node> &q) {
	int u=q.top().u,i=q.top().i,v=g[u][i].v;
	ll d=q.top().d;
	q.pop();
	if(i+1<(int)g[u].size())q.push({u,i+1,dis[u]+g[u][i+1].w});
	if(vis[v])return 0;
	vis[v]=1,dis[v]=d,vec.push_back(v);
	if(vis0[v])return v;
	if(!g[v].empty())q.push({v,0,d+g[v].front().w});
	return 0;
}
ll Dij(int S,int T) {
	if(S==T)return 0;
	if(g[0][S].empty()||g[1][T].empty())return -1;
	int tmp=0;
	vector<int> vec[2] {{S},{T}};
	priority_queue<node> q[2];
	dis[0][S]=0,vis[0][S]=1,q[0].push({S,0,g[0][S].front().w});
	dis[1][T]=0,vis[1][T]=1,q[1].push({T,0,g[1][T].front().w});
	for(bool ty=(q[0].size()>q[1].size()); !tmp&&!q[0].empty()&&!q[1].empty(); ty=(q[0].size()>q[1].size()))
		tmp=Relax(vis[ty],vis[ty^1],dis[ty],vec[ty],g[ty],q[ty]);
	while(!q[0].empty())q[0].pop();
	while(!q[1].empty())q[1].pop();
	if(!tmp) {
		FOR(ty,0,1)for(const int &u:vec[ty])vis[ty][u]=0;
		vec[0].clear(),vec[1].clear();
		return -1;
	}
	ll res=dis[0][tmp]+dis[1][tmp];
	FOR(ty,0,1)for(const int &u:vec[ty])for(const edge &e:g[ty][u]){
		if(e.w>=((dis[ty][tmp]-dis[ty][u])<<1))break;
		if(vis[!ty][e.v])tomin(res,dis[ty][u]+e.w+dis[!ty][e.v]);
	}
	FOR(ty,0,1)for(const int &u:vec[ty])vis[ty][u]=0;
	vec[0].clear(),vec[1].clear();
	return res;
}
signed main() {
	cin>>n>>m>>Q>>Seed;
	mt19937 rng(Seed);
	auto sample = [&]() {
		ui x;
		static const ui lim=-1u/n*n;
		do x=rng();
		while(x>=lim);
		return x%n+1;
	};
	FOR(i,1,m) {
		int u=sample(),v=sample();
		ui w=rng();
		g[0][u].push_back({v,w}),g[1][v].push_back({u,w});
	}
	FOR(ty,0,1)FOR(i,1,n)sort(g[ty][i].begin(),g[ty][i].end());//边排序,等遍历到一个后再加下一个
	for(int S,T; Q; --Q)cin>>S>>T,cout<<Dij(S,T)<<endl;
	return 0;
}
/*
双向 Dijkstra,那么最终点数为 O(sqrt(n)) 级别.
用特殊形式的 Dijkstra ,使得单次 Dijkstra 时间复杂度在 O(sqrt(n)\log_{2}{n})
Dijkstra 后,枚举相遇边,求得答案.
*/