Problem Description

Given an unrooted tree with $n$ nodes, the distance between adjacent nodes is $1$. At the beginning, you are at node $m$. Then you will receive $k$ commands one by one. Each command contains two integers $d$ and $t$. You need to move toward node $d$ along the shortest path within $t$ steps (including exactly $t$ steps). If you cannot reach $d$ within $t$ steps, then you stop at the last node you can reach. After each command, output your current position.

Input Format

The first line contains three integers $n, m, k$.

The next $n - 1$ lines each contain two integers $x, y$, representing an edge of the tree.

The next $k$ lines each contain two integers $d, t$, representing a command.

Output Format

One line containing $k$ integers, where the $i$-th integer is the node you are at after executing the $i$-th command.

3 1 2
1 2
2 3
3 4
1 1

3 2

Hint

For $100\%$ of the data, $1 \leq m \leq n \leq 10^6$, $1 \leq k \leq 10^6$, $1 \leq x, y, d \leq n$, $0 \leq t \leq 10^9$.

Translated by ChatGPT 5