A16716 | Idiot First Search and Queries

本题与 E 题使用相同的定义。但本题并不要求与 E 题相同的答案。

有一棵包含 $n+1$ 个顶点的二叉树（$n$ 为奇数），顶点编号为 $0,1,\ldots,n$。每个顶点上最多可以写一个字母，一开始所有顶点上都没有写字母。树的根节点是顶点 $0$。

在树中，顶点 $0$ 是顶点 $1$ 的父节点，其余顶点要么有 $2$ 个子节点，要么没有子节点。

Bob 迷失在树的某个顶点，他希望通过到达顶点 $0$ 的方式逃出树。对于大多数有常识的人来说，这很容易。但由于 Bob 很笨，他发明了一种全新的遍历树的方法，被称为“笨蛋优先遍历法”（"Idiot First Search"）。

当 Bob 处于顶点 $v$ 时（$1 \le v \le n$），他按照如下规则移动：

- 如果顶点 $v$ 是叶节点，Bob 总是移动到 $v$ 的父节点；否则，继续判断以下情况。
- 如果顶点 $v$ 上什么都没写，Bob 在顶点 $v$ 上写下 'L'，并移动到 $v$ 的左儿子；
- 如果顶点 $v$ 上写有字母 'L'，Bob 将其覆盖为 'R'，并移动到 $v$ 的右儿子；
- 如果顶点 $v$ 上写有字母 'R'，Bob 擦除它，移动到 $v$ 的父节点。

Bob 移动到相邻顶点每次正好需要 $1$ 秒，因此进行 $x$ 次移动总共需要 $x$ 秒。

已经证明，无论 Bob 从哪一个顶点出发，都能在有限（尽管可能非常大）的时间内到达顶点 $0$。我们不知道是谁证明了这点，肯定不是 Bob，但这一点确实被证明了。

你需要回答 $q$ 个如下类型的询问：

- $v\;k$：假设 Bob 从顶点 $v$ 出发，恰好经过 $k$ 次移动后，Bob 处于哪个顶点（$1 \le v \le n$）。

对于每个询问，设 $T_v$ 表示 Bob 从顶点 $v$ 到达顶点 $0$ 的所需时间。保证每个询问 $k < T_v$。

每个测试点包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的数据。

每个测试用例的第一行包含整数 $n$ 和 $q$（$1 \le n \le 300\,001$，$1 \le q \le 400\,000$，$n$ 为奇数）。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$，分别为顶点 $i$ 的左右子节点编号（$0 \le l_i,r_i \le n$）。

对于每个顶点，如果 $l_i = r_i = 0$，则表示该顶点没有子节点。否则，$l_i$ 和 $r_i$ 分别为顶点 $i$ 的左儿子和右儿子。

接下来的 $q$ 行，每行包含两个整数 $v_j$ 和 $k_j$，表示第 $j$ 个询问（$1 \le v_j \le n$，$0 \le k_j < \min(10^9+7, T_{v_j})$）。

保证输入描述的是一棵合法的二叉树，满足题目中所述的条件。

且所有测试用例中的 $n$ 之和不超过 $300\,001$。

所有测试用例中的 $q$ 之和不超过 $400\,000$。

对于每个测试用例，按询问顺序依次输出每个询问的答案，每个测试用例输出一行。