Problem Description

For two rooted binary trees $T_1, T_2$, define the result of $\operatorname{merge}(T_1,T_2)$ as a binary tree whose root’s left subtree is $T_1$ and right subtree is $T_2$. Obviously, the result of $\operatorname{merge}(T_1,T_2)$ is unique and always exists.

For a rooted binary tree $T$, define a function $G_x(T)$. Here, $G_1(T)$ means: starting from the root of $T$, keep moving to the right child until reaching a node that has no right child; then set that node’s right subtree to be $T$. The resulting new tree is $G_1(T)$. For $x>1$, $G_x(T)$ satisfies:

$$G_x(T)=G_1(\operatorname{merge}(G_{x-1}(T),G_{x-1}(T)))$$

Given a rooted binary tree with $n$ nodes and root $1$, let the subtree rooted at node $i$ be $T_i$. There are $q$ queries. Each query gives $x,i$. For each query, find the maximum independent set of $G_x(T_i)$.

Input Format

The first line contains two integers $n,q$.

Then follow $n$ lines. Each line contains two integers $ls_i,rs_i$, representing the left child and right child. If it is $0$, it means the corresponding child does not exist.

Then follow $q$ lines. Each line contains two integers $x,i$, representing one query.

Output Format

Output $q$ lines. Each line contains one number: the size of the maximum independent set of $G_x(T_i)$ modulo $998244353$ for this query.

5 3
2 3
0 4
5 0
0 0 
0 0
2 5 
2 1
1 1

5
24
6

5 1
2 3
0 4
5 0
0 0 
0 0
64 1

592424678

Hint

Sample Explanation

For the first sample, the result of $G_2(T_5)$ is shown in the figure below (node indices are ignored):

For the second sample, I have a wonderful explanation, but unfortunately $G_{64}$ is too large to write it down here.

Constraints and Notes

This problem enables bundled testdata and O2 optimization.

Subtask	Constraints / Special Properties	Score
$1$	$n,q,x\le 10$	$10 \operatorname{pts}$
$2$	$x =1$	$5 \operatorname{pts}$
$3$	$x\le 3$	$10 \operatorname{pts}$
$4$	$x\le 10$	$15 \operatorname{pts}$
$5$	The size of $T_i$ is guaranteed to be $1$	$10 \operatorname{pts}$
$6$	No special restrictions	$50 \operatorname{pts}$

For $100\%$ of the testdata: $1\le x\le 10^9$, $1\le n\le 5\times 10^5$, $1\le q\le 5\times 10^5$.

Translated by ChatGPT 5