#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a,i##E=b;i<=i##E;i++)
#define UF(i,a,b) for(int i=a,i##E=b;i>=i##E;i--)
#define sz(x) int(x.size())
using namespace std;typedef long long ll;
#define vec vector
template<typename T>
void operator+=(vec<T> &a,const T&b) {a.push_back(b);}
#define gc() getchar()
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char *p1,*p2,buf[1<<21];
unsigned read() {
	unsigned s=0,w=0;char ch=gc();
	while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
	return w?-s:s;
}
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
    std::mt19937 gen(seed);
    std::vector<std::tuple<int, int, long long>> edges(m);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
    for(auto & [u, v, w] : edges) {
        u = sample();
        v = sample();
        w = gen();
    } // u 到 v 存在边权为 w 的边
    return edges;
} const int N=2e5+5;
const ll inf=1e18;
int n,m,q;
struct E{int v;ll w;bool operator<(E b)const{return w<b.w;}};
vec<E> G[N][2];
using T=tuple<ll,int,int>;
ll d[N][2];int now[N][2],vis[N][2];
ll sol(int s,int t) {
	if(s==t) return 0; 
	if(!sz(G[s][0])||!sz(G[t][1])) return -1;
	priority_queue<T,vec<T>,greater<T>> q[2];
	auto Push=[&](int x,int i,int r,const int type=0) {
		if(i>=sz(G[x][r])) return;
		auto[v,w]=G[x][r][i];
		if(d[x][r]+w<d[v][r]) q[r].push({d[v][r]=d[x][r]+w,v,x});
		else if(type) q[r].push({d[v][r],v,x});
	};
	d[s][0]=0;d[t][1]=0;
	vis[s][0]=vis[t][1]=1;
	Push(s,0,0,1);Push(t,0,1,1);
	vec<int> V[2];
	int X=-1;V[0]+=s;V[1]+=t;ll ans=inf;
	while(sz(q[0])&&sz(q[1])) {
		int r=sz(V[0])>sz(V[1]);
		auto[D,x,p]=q[r].top();q[r].pop();
		Push(p,++now[p][r],r,1);
		if(D>d[x][r]) continue;
		vis[x][r]=1;V[r]+=x;
		if(vis[x][0]&&vis[x][1]) {/*cerr<<"X:"<<x<<endl;*/X=x;ans=d[x][0]+d[x][1];break;}
		Push(x,0,r);
	} //cerr<<"SZ:"<<sz(V[0])<<' '<<sz(V[1])<<endl;
	#define x X
	if(~x) {
		for(int y:V[0]) for(auto[v,w]:G[y][0]) 
//			if(w<2*(d[x][0]-d[y][0])) 
			ans=min(ans,d[y][0]+w+d[v][1]);
//		else break;
		for(int y:V[1]) for(auto[v,w]:G[y][1]) 
//			if(w<2*(d[x][1]-d[y][1])) 
			ans=min(ans,d[y][1]+w+d[v][0]);
//		else break;
	}
	auto clr=[&](int x) {d[x][0]=d[x][1]=inf;now[x][0]=now[x][1]=0;vis[x][0]=vis[x][1]=0;};
	for(int y:V[0]) clr(y);
	for(int y:V[1]) clr(y);
	while(sz(q[0])) {
		auto[D,x,p]=q[0].top();q[0].pop();
		clr(x);clr(p);
	}
	while(sz(q[1])) {
		auto[D,x,p]=q[1].top();q[1].pop();
		clr(x);clr(p);
	}
	return ans>=inf?-1:ans;
	#undef x
}
unsigned seed;
int main() {
	n=read();m=read();q=read();
	auto Edges=generate_edges(n,m,seed=read());
	for(auto[u,v,w]:Edges) G[u][0]+=E{v,w},G[v][1]+=E{u,w};//,cerr<<"K::"<<u<<' '<<v<<' '<<w<<endl;
	F(i,1,n) F(j,0,1) sort(begin(G[i][j]),end(G[i][j]));
	F(j,0,1) F(i,1,n) d[i][j]=inf;
//	if(n>2000) return 0;
	F(i,1,q) {
		int x=read(),y=read();
//		if(seed==1526732796u) {
//			if(i==106) cout<<x<<' '<<y<<endl;
//		} else
		cout<<sol(x,y)<<'\n';
	}
	return 0;
}