Taco: K-th Ancestor Problem

You are given an undirected tree with N vertices numbered from 1 to N. The tree is rooted at node 1. For Q queries, each given as a pair (x, k), your task is to find the k-th ancestor of node x. If node x does not have a k-th ancestor, output -1.

Formally, if we denote the parent of a node v by \(P(v)\), the k-th ancestor is defined recursively as:

[ A(v, k) = \begin{cases} v & \text{if } k = 0, \ P(v) & \text{if } k = 1, \ A(P(v), k-1) & \text{if } k > 1. \end{cases} ]

You are required to answer each query efficiently. Binary lifting is one of the common techniques to achieve an efficient solution.

Example:

Input:
7 4
1 2
1 3
2 4
2 5
3 6
3 7
4 1
5 2
6 1
6 3
Output:
2 1 3 -1

</p>

inputFormat

The first line contains two integers N and Q, representing the number of vertices and the number of queries respectively.

Each of the next N - 1 lines contains two integers u and v, indicating that there is an edge between vertices u and v.

The following Q lines each contain two integers x and k, representing a query to find the k-th ancestor of node x.

outputFormat

Output a single line with Q integers separated by a space, where each integer is the answer to the corresponding query. If the k-th ancestor does not exist, output -1 for that query.

## sample

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

2 1 3 -1

</p>