题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 与顶点 $v_i$。

若顶点集合 $S$ 中任意两个不同顶点在树上都不相邻，则称 $S$ 为一个独立集。

对于顶点 $v$，记 $F_v$ 为所有满足 $v\in S$ 的独立集 $S$ 所组成的集合。

回答 $Q$ 个询问。每个询问给出整数 $v,q$，计算

$$\left(\sum_{S\in F_v}q^{|S|}\right)\bmod 998244353,$$

其中 $|S|$ 表示集合 $S$ 的大小。

限制条件

• $2\le N\le 1.3\times 10^5$
• $1\le Q\le 1.3\times 10^5$
• $1\le u_i<v_i\le N$
• 输入给出的图是一棵树。
• $1\le v\le N$
• $1\le q<998244353$
• 所有输入均为整数。

部分分

• 对所有询问都满足 $v=1$ 的数据求解正确，可获得 $5$ 分。

输入

N Q
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
v_1 q_1
v_2 q_2
...
v_Q q_Q

输出

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

样例输入 1

4 2
1 2
1 3
2 4
1 1
2 3

样例输出 1

2
12

对于第一个询问，包含顶点 $1$ 的独立集为 $\{1\}$ 和 $\{1,4\}$，因此答案为

$$1^1+1^2=2.$$

样例输入 2

10 10
1 2
2 3
1 4
1 5
1 6
6 7
6 8
5 9
1 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

样例输出 2

16
162
768
2500
6480
14406
28672
52488
90000
146410

样例输入 3

10 10
1 2
1 3
2 4
4 5
4 6
2 7
5 8
8 9
6 10
5 844033520
8 780395612
2 285523486
6 13801767
3 487663185
3 667406485
7 672229269
7 207478896
5 769551740
7 806405364

样例输出 3

665599367
675643489
193550820
987507475
230555342
555586355
204648376
83113599
299301383
545057926