Description
Given a tree with N nodes and Q queries, each query specifies a start point S, an endpoint T, and a number K.
For each query, the question asks for the node at the K-th step on the path from S to T.
(Tree from sample input)
Input
The first line contains two numbers N and Q, where N ≤ 500,000 and Q ≤ 1000,000 indicating that the tree has N nodes and Q queries.
The next N−1 lines each contain two numbers A and B, indicating that there is an edge between A and B.
Following this, there are Q lines, each containing three numbers S, T, and K, indicating the query for the node reached by moving K steps from S towards T.
It is guaranteed that A, B, S, and T are all positive integers from 1 to N, and K is integer from 0 to N.
Output
The output consists of Q lines, each containing a single number that represents the node reached by moving K steps from S towards T.
If K is greater than the number of steps from S to T, output −1.