#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 23 | 15 | 1s | 256MB | Minimum |

2 | 28 | 10 | 1s | 256MB | Minimum |

3 | 49 | 45 | 1s | 256MB | Minimum |

4 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o ancestor -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512