#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 200005
vector<pair<int,int>> G[2][N];
int n,m,Q;
void generate_edges(int n, int m) {
	unsigned seed; cin>>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,v,w;
        u = sample();
        v = sample();
        w = gen();
        // printf("%lld %lld %lld\n",u,v,w);
        G[0][u].emplace_back(v,w);
        G[1][v].emplace_back(u,w);
    } // u 到 v 存在边权为 w 的边=
}
struct Node
{
	int u,w,uu,id;
	Node(int a=0,int b=0,int c=-1,int d=-1)
	{
		u=a,w=b,uu=c,id=d;
	}
	bool operator < (const Node &x) const
	{
		return w>x.w;
	}
};
int dis[2][N],lst[2][N];
priority_queue<Node> q[2];
vector<int> nd[2];
signed main()
{
	cin>>n>>m>>Q;
	generate_edges(n, m);
	for(int t=0;t<2;t++) for(int i=1;i<=n;i++)
	{
		sort(G[t][i].begin(),G[t][i].end(),[&](auto u,auto v){
			return u.second<v.second;
		});
	}
	for(int t=1;t<=Q;t++)
	{
		int u=read(),v=read();
		// q[0].clear(),q[1].clear();
		while(!q[0].empty()) q[0].pop();
		while(!q[1].empty()) q[1].pop();
		dis[0][u]=0,dis[1][v]=0;
		lst[0][u]=t,lst[1][v]=t;
		q[0].emplace(u,0);
		q[1].emplace(v,0);
		int ok=0;
		for(int op=0;ok==0;op^=1)
		{
			if(q[op].empty())
			{
				ok=1;
				break;
			}
			auto [u,w,uu,id]=q[op].top(); q[op].pop();
			if(dis[op][u]!=w) {op^=1; continue;}
			// printf("%d : %d %d %d %d\n",op,u,w,uu,id);
			auto push=[&](int uu,int id){
				while(id+1!=(int)G[op][uu].size())
				{
					id++;
					auto [v,e]=G[op][uu][id];
					if(lst[op][v]!=t||dis[op][v]>w+e)
					{
						if(lst[op][v]!=t) nd[op].push_back(v);
						lst[op][v]=t,dis[op][v]=w+e;
						if(lst[op^1][v]==t) ok=2;
						q[op].emplace(v,w+e,uu,id);
						break;
					}
				}
			};
			if(uu!=-1) push(uu,id);
			push(u,-1);
		}
		if(ok==1) printf("-1\n");
		else
		{
			int ans=INF;
			for(int u:nd[0])
			{
				for(auto [v,w]:G[0][u])
				{
					if(lst[1][v]==t) ans=min(ans,dis[0][u]+w+dis[1][v]);
				}
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}