### ** ancestor**

## Problem Description

You are given a connected tree with *N* nodes and *N-1* edges, rooted at node 0.

Rar the Cat wants you to answer *Q* queries regarding the tree. For each query, you will be provided with 2 integers, *X* and *K*. You are to output the *K*^{th} parent of the *X* node. In the event that node *X* does not have that many parent nodes, print -1 instead.

## Limits

For all testcases, 0 ≤ *A*, *B* < *N* and 0 < *X* < *N*

Subtask 1 (23%): 1 ≤ N ≤ 1000, 1 ≤ Q ≤ 5000

Subtask 2 (28%): 1 ≤ N ≤ 100000, 1 ≤ Q ≤ 500000. However, each node can at most have 2 edges.

Subtask 3 (49%): 1 ≤ N ≤ 100000, 1 ≤ Q ≤ 500000.

Subtask 4 (0%): Sample Testcases.

## Input

The first line of input will contain one integer, *N*.

The following *N-1* lines will contain 2 integers each, *A* and *B*. This denotes that there is an edge between node *A* and node *B*.

As the resulting tree is guaranteed to be connected, do note that A will not be equal to B. Also, no two pairs of A and B will be the same.

The next line of input will contain *Q*, the number of queries.

The following *Q* lines will contain 2 integers each, *X* and *K*.

## Output

You are to output *Q* lines of 1 integer each, one per query.

For each query, you are to output the *K*^{th} parent of node *X*. Print -1 instead of node *X* does not have *K* parents.

## Sample Testcase 1

### Input

10
0 1
1 2
2 3
3 4
4 5
6 0
7 2
2 8
3 9
5
5 3
5 5
7 2
6 2
8 2

### Output

2
0
1
-1
1