Given an undirected rooted tree at node 1, consisting of N nodes. Find the kth ancestor of a given node. There will be Q queries.

Input:

First line contains N, the number of nodes in the tree. Next N - 1 lines contains two integers u and v, there is an edge between u and v. Next line contains Q, the number of queries. Each of the next Q lines contains a node p and and integer k.

Output:

Print on a single line the answer of query as described.

Constraints:

\( 1 \leq N,k,p \leq 10^5 \)

\( 1 \leq Q \leq 10^5 \)

\( 1 \leq u , v \leq 10^5 \)

Update: In case No ancestor exists, output root node i.e, 1.

Problem Setter - Saurabh