You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在 5202 年 3 月 23 日的中午 12:00，你转世来到了 USTCPC2025 的赛场上。你只记得上一世你只做出了 2 道题（是吗？）。

这一次，你打算一雪前耻，但是发现题目怎么变了？

题目描述

给定一个随机生成的 $n$ 个点，$m$ 条边的无向图。第 $i$ 条边 $(u_i,v_i)$ 有一个随机生成的非负边权 $a_i$。

对于任何一条路径/轨道，定义其代价：设路径为 $(p_0,p_1,...,p_k)$，其中要求 $(p_{i-1},p_i)$ 是无向图中的边，设其为第 $e_i$ 条边。那么路径的代价即为 $\mathop{\text{mex}}\limits_{i=1}^{k} a_{e_i}$。（该路径可以经过重复点和重复边，即 $p$ 和 $e$ 可以包含重复的数）

$\text{mex}$ 是一种定义域为一个非负整数的可重集合，函数值为非负整数的映射，定义为最小的未在集合内出现过的非负整数。

定义 $f(x,y)$ 为从 $x$ 到 $y$ 的所有路径/轨道中代价的最小值。特别地，当 $x=y$ 时，$f(x,y)=0$；如果从 $x$ 到 $y$ 不存在路径，那么 $f(x,y)=-1$。

之后，有 $q$ 组询问：给定参数 $(x,y)$，你需要求出 $f(x,y)$。

输入格式

第一行三个正整数 $n,m,q$ ($1\le n,m,q\le 10^5$)。

第 $2\sim m+1$ 行，每行两个正整数 $u_i,v_i$ ($1\le u_i,v_i\le n$) 和一个非负整数 $a_i$ ($0\le a_i<2^{31}$)。

图的随机方式：给定参数 $n,m$ 和 $p\in [0.0001,1)$，$u_i,v_i$ 从 $[1,n]$ 中均匀随机生成，$a_i+1$ 服从参数为 $p$ 的几何分布。几何分布的定义为 $P(x=k)=(1-p)^{k-1} p, k=1,2\cdots$。

第 $m+2\sim m+q+1$ 行，每行两个正整数 $x,y$ ($1\le x,y\le n$) 表示询问。

输出格式

输出共 $q$ 行，每行一个整数表示答案。

样例 #1

样例输入 #1

4 4 3
1 2 0
2 3 1
3 1 2
3 4 0
1 2
3 4
2 4

样例输出 #1

0
1
1

样例 #2

样例输入 #2

2 1 2
1 1 1
1 1
1 2

样例输出 #2

0
-1

提示

考虑 $f(1,2)$：

• 考虑路径 $1\rightarrow 2$，路径的代价为 $\text{mex}\{0\}=1$。
• 考虑路径 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2$，路径的代价为 $\text{mex}\{0,1,2,0\}=3$。
• 考虑路径 $1\rightarrow 3\rightarrow 2$，路径的代价为 $\text{mex}\{1,2\}=0$。

此外还存在其他路径，但可以证明不存在代价比 $0$ 更小的路径，故 $f(1,2)=0$。