H. Ant MRT
time limit per test
3.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are conducting a study on an ant nest modeled as a tree with $$$n$$$ nodes. This ant colony happens to be very technologically advanced and they have $$$m$$$ MRT companies. The route for company $$$i$$$ is the path between $$$a_i$$$ and $$$b_i$$$. If you buy a pass for $$$c_i$$$ NT dollars, you will be able to travel between any pair of nodes on the path.

As part of your research, you need to find out how much the ants pay for their daily commute. You have to answer $$$q$$$ questions, the $$$j$$$-th question asks for the minimum amount of money (in NT dollars) you need to travel from $$$u_j$$$ to $$$v_j$$$ or $$$-1$$$ if it's impossible.

Input

The first line contains three integers $$$n, m, q$$$ ($$$2 \le n, m, q \le 10^5$$$).

Then $$$n - 1$$$ lines follow, each containing two integers $$$s, t$$$ ($$$1 \le s, t \le n, s \ne t$$$) denoting an edge between the $$$s$$$-th and $$$t$$$-th nodes in the ant nest. It is guaranteed that the given edges form a tree.

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains three integers $$$a_i, b_i, c_i$$$ ($$$1 \le a_i, b_i \le n, a_i \ne b_i, 0 \le c_i \le 6$$$) describing the route for the $$$i$$$-th MRT company.

Then $$$q$$$ lines follow. The $$$j$$$-th of them contains two integers $$$u_j, v_j$$$ ($$$1 \le u_j, v_j \le n$$$) denoting the $$$j$$$-th question.

Output

For each question, output its answer on one line.

Scoring
  • Subtask 1 (9 points): $$$n \le 1000$$$
  • Subtask 2 (20 points): $$$n, m \le 4000$$$
  • Subtask 3 (22 points): For $$$i=1,2,\dots,m$$$, node $$$a_i$$$ is on the shortest path between node 1 and node $$$b_i$$$.
  • Subtask 4 (18 points): For $$$i=1,2,\dots,m$$$, $$$c_i \le 1$$$
  • Subtask 5 (27 points): For $$$i=1,2,\dots,m$$$, $$$c_i \le 5$$$
  • Subtask 6 (4 points): No additional constraints
Example
Input
5 2 8
1 2
1 3
1 4
4 5
2 3 1
2 4 2
1 1
1 2
1 3
1 4
2 3
2 4
3 4
3 5
Output
0
1
1
2
1
2
3
-1