题目描述

给定一棵 $n$ 个点的无根树，相邻的点之间的距离为 $1$，一开始你位于 $m$ 点。之后你将依次收到 $k$ 个指令，每个指令包含两个整数 $d$ 和 $t$，你需要沿着最短路在 $t$ 步之内（包含 $t$ 步）走到 $d$ 点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。

输入格式

第一行，三个整数 $n, m, k$；

接下来 $n - 1$ 行，每行两个整数 $x, y$，表示一条树边；

接下来 $k$ 行，每行两个整数 $d, t$，表示一条指令。

输出格式

一行，$k$ 个整数，表示执行对应指令后你所在的位置。

3 1 2
1 2
2 3
3 4
1 1

3 2

提示

对于 $100\%$ 的数据，$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$。