CF2195G.Idiot First Search and Queries

This problem shares the definitions with problem E. However, it does not ask for the same answer.

There is a binary tree of $n+1$ vertices ($n$ is odd), with vertices labeled $0,1,\ldots,n$. At most one letter can be written on each vertex of the tree, and all vertices initially have nothing written on them. The root of the tree is vertex $0$.

In the tree, vertex $0$ is the parent of vertex $1$, while all other vertices have either $2$ children or $0$ children.

Bob is lost in one vertex of the tree and wishes to escape the tree by reaching vertex $0$. This is very easy for most people with common sense. However, since Bob is an idiot, he created a new way of traversing the tree; introducing the "Idiot First Search".

When Bob is on vertex $v$ ($1 \le v \le n$), Bob's movement is determined as follows:

• If vertex $v$ is a leaf, Bob always moves to the parent of $v$; otherwise, check the next few conditions.
• If nothing is written on vertex $v$, Bob writes 'L' on vertex $v$ and moves to the left child of $v$;
• If 'L' is written on vertex $v$, Bob overwrites it to 'R' and moves to the right child of $v$;
• If 'R' is written on vertex $v$, Bob erases it and moves to the parent of $v$.

It takes exactly $1$ second for Bob to move to an adjacent vertex, so Bob will take exactly $x$ seconds to perform $x$ moves.

It has been shown that regardless of which vertex Bob starts on, Bob can reach vertex $0$ in a finite (though possibly inexplicably large) amount of time. We don't know who proved it; surely it can't be Bob, but it is definitely proven.

You are asked to answer $q$ queries of the following kind:

• $v\;k$: Assuming that Bob started from vertex $v$, determine the vertex Bob is on after performing exactly $k$ moves ($1 \le v \le n$).

For each query, let $T_v$ be the time taken to reach vertex $0$ from vertex $v$. Then, it is guaranteed that $k \lt T_v$ for every query.

本题沿用问题 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$ 次移动后所在的顶点（其中 $1 \le v \le n$）。

对每个查询，记 $T_v$ 为 Bob 从顶点 $v$ 到达顶点 $0$ 所需的时间。题目保证对每个查询均有 $k \lt T_v$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains integers $n$ and $q$ ($1 \le n \le 300\,001$, $1 \le q \le 400\,000$, $n$ is odd).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ denoting the children of vertex $i$ ($0 \le l_i,r_i \le n$).

For each vertex, $l_i=r_i=0$ is given if the vertex has no children. Otherwise, $l_i$ and $r_i$ are the left and right children of vertex $i$.

Each of the next $q$ lines contains two integers $v_j$ and $k_j$ denoting the $j$-th query ($1 \le v_j \le n$, $0 \le k_j \color{red}{ \lt } \min(10^9+7,T_{v_j})$).

It is guaranteed that the input defines a valid binary tree satisfying the conditions given in the statement.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,001$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $400\,000$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

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

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示顶点 $i$ 的左右子节点（$0 \le l_i,r_i \le n$）。

对每个顶点，若其无子节点，则给出 $l_i = r_i = 0$；否则，$l_i$ 和 $r_i$ 分别为其左、右子节点。

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

保证输入定义了一棵满足题目所述条件的有效二叉树。

保证所有测试用例中 $n$ 的总和不超过 $300\,001$。

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

For each test case, output the answers to the $q$ queries on a separate line.

对于每个测试用例，将 $q$ 个查询的答案分别输出在单独的行上。

On the first test case, there are only two vertices, vertex $0$ and vertex $1$. Obviously, Bob will be on vertex $1$ when $0$ moves have been performed after Bob started from vertex $1$.

On the second test case, the tree is given as follows.

It takes $14$ seconds for Bob to reach vertex $0$ from vertex $3$. The moves are as follows:

$$3 \\xrightarrow{\\mathtt{L}} 4 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{R}} 5 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{L}} \\color{red}{2} \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{R}} \\color{red}{3} \\xrightarrow{\\mathtt{L}} 4 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{R}} \\color{red}{5} \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{X}} 0$$

Here, the letters above the arrows denote the letter on the vertex before moving to the adjacent vertex, where $\mathtt{X}$ denotes nothing written.

As highlighted in red, it is shown that:

• Bob is on vertex $2$ when $6$ moves have been performed after Bob started on vertex $3$;
• Bob is on vertex $3$ when $8$ moves have been performed after Bob started on vertex $3$;
• Bob is on vertex $5$ when $11$ moves have been performed after Bob started on vertex $3$.

在第一个测试用例中，图中仅有两个顶点：顶点 $0$ 和顶点 $1$。显然，当 Bob 从顶点 $1$ 出发、执行 $0$ 次移动后，他将位于顶点 $1$。

在第二个测试用例中，该树如下所示。

Bob 从顶点 $3$ 出发，需耗时 $14$ 秒才能到达顶点 $0$。其移动过程如下：

$$3 \\xrightarrow{\\mathtt{L}} 4 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{R}} 5 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{L}} \\color{red}{2} \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{R}} \\color{red}{3} \\xrightarrow{\\mathtt{L}} 4 \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{R}} \\color{red}{5} \\xrightarrow{\\mathtt{X}} 3 \\xrightarrow{\\mathtt{X}} 1 \\xrightarrow{\\mathtt{X}} 0$$

其中，箭头上的字母表示在移向相邻顶点前，当前顶点上所写的字母；$\mathtt{X}$ 表示该顶点上未写任何字母。

如红色高亮所示：

• Bob 从顶点 $3$ 出发、执行 $6$ 次移动后，位于顶点 $2$；
• Bob 从顶点 $3$ 出发、执行 $8$ 次移动后，位于顶点 $3$；
• Bob 从顶点 $3$ 出发、执行 $11$ 次移动后，位于顶点 $5$。