There is a tree with n vertices rooted at node 1.

You have to given Q queries.Each query have two integer a and b, you have to tell bth parent of ath node.  

Input

• The first line contains two integers n ,q.
• Next n-1 lines contains three integers u and v (1≤u,v≤n,u≠v), denoting an edge from u to v. 
• Next Q lines contains a and b.

Output

• Print the bth parent of ath node or print -1 if parent do not exist.

Constraints

• 2≤n≤2⋅10^5
• 2≤q≤10^5