[ONTAK2015] Związek Harcerstwa Bajtockiego

题目描述

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

输入输出格式

输入格式


第一行,三个整数 $n, m, k$; 接下来 $n - 1$ 行,每行两个整数 $x, y$,表示一条树边; 接下来 $k$ 行,每行两个整数 $d, t$,表示一条指令。

输出格式


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

输入输出样例

输入样例 #1

3 1 2
1 2
2 3
3 4
1 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$。