Problem Description

There is a local area network consisting of $n$ devices and $m$ physical connections. The stability of the $i$-th connection is $w_i$.

For a path from device $A$ to device $B$ that passes through several physical connections, we define the stability of this path as the minimum stability among all connections on the path.

We define the communication stability between device $A$ and device $B$ as the maximum stability among all feasible paths from $A$ to $B$.

Given the physical connection information in the LAN, compute the communication stability for several pairs of devices $x_i$ and $y_i$. If there is no path between two devices, output $-1$.

Input Format

The first line contains three integers $n, m, q$, representing the number of devices, the number of physical connections, and the number of queries.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, meaning there is a physical connection between $u_i$ and $v_i$ with stability $w_i$.

The next $q$ lines each contain two integers $x_i, y_i$, asking for the communication stability between $x_i$ and $y_i$.

Output Format

Output $q$ lines. Each line contains one integer, in order, representing the answer to each query.

5 4 3
1 2 5
2 3 6
3 4 1
1 4 3
1 5
2 4
1 3

-1
3
5

Hint

[Scale and constraints of testdata]

For $30\%$ of the testdata, $n, q \leq 500$, $m \leq 1000$.

For $60\%$ of the testdata, $n, q \leq 5000$, $m \leq 10000$.

For all testdata, $2 \leq n, q \leq 10^5$, $1 \leq m \leq 3 \times 10^5$, $1 \leq u_i, v_i, x_i, y_i \leq n$, $1 \leq w_i \leq 10^6$, $u_i \neq v_i$, $x_i \neq y_i$.

Translated by ChatGPT 5