407771: GYM102891 H Ant MRT

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.

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.

For each question, output its answer on one line.

• 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

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

0
1
1
2
1
2
3
-1