You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一片由树形迷宫组成的奇幻森林里，所有道路连通成一棵无根树，我们将1号节点定为树根，这里是小Y心心念念的家。整座迷宫没有环路、没有孤立区域，每个非根节点都只有一条通往根节点的向上路径，结构全程固定，不会发生任何变化。

小Y被困在迷宫的某个节点上，他唯一的目标就是沿着迷宫道路，一步步走回1号节点的家中。可这座迷宫被施加了特殊的随机魔法，行走规则被严格限定，小Y只能依靠自己的智慧和有限的道具，尽可能掌控随机性，顺利抵达终点。

• 小Y每完成一次移动算作一步，步数从1开始依次递增，每一步的行动模式，完全由当前步数是奇数步还是偶数步决定，没有任何变通余地：
• 奇数步（第1、3、5……步）：强制定向，无随机可能 每当轮到奇数步移动，迷宫的强制魔法会立刻生效，小Y必须朝着根节点1的方向向上走一步，没有其他任何选择。这一步完全可控，不会出现任何随机偏移，能稳稳朝着家的方向靠近一步。
• 偶数步（第2、4、6……步）：随机失控，硬币可控 偶数步是整场闯关中最不确定的时刻，迷宫的随机魔法会彻底爆发：如果小Y不借助道具干预，他会等概率随机走向当前节点的任意一个相邻节点，有可能碰巧向上靠近家，也有可能走回原路、甚至偏向其他分支，彻底偏离回家路线，随机性完全不受自身控制。 好在小Y随身携带了特殊的掌控硬币，这是他对抗随机魔法的唯一法宝。每到偶数步，只要花费1枚掌控硬币，就能暂时破除随机魔法，强制自己和奇数步一样，稳稳朝着根节点1的方向向上走一步，彻底规避随机风险，牢牢把控行进方向。

定义$f(v,p)$为小Y当前在v点，还有p枚硬币情况下走到家的期望步数。
你需要帮助小Y计算 $q$ 个询问。每个查询包含一对 $(v_i, p_i)$，你需要计算 $f(v_i, p_i)$ 模 $998\,244\,353$ 的值。

具体来说，令 $M = 998\,244\,353$。结果可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。你需要输出 $p \cdot q^{-1} \bmod M$。换句话说，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

输入格式

输入包含多个测试用例。第一行为测试用例的数量 $t$ （$1 \le t \le 10^3$）。

对于每个测试用例，第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2000$，$1 \le q \le 2000$），分别表示树的顶点数和查询数量。

接下来的 $n - 1$ 行每行描述一条树的边，包含两个整数 $u_i$ 和 $v_i$ （$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示节点 $u_i$ 和 $v_i$ 之间有一条边。

接下来的 $q$ 行中每行包含两个整数 $v_i$ 和 $p_i$（$2 \le v_i \le n$，$0 \le p_i \le n$），表示每个查询的节点和初始硬币数。

保证输入的边构成一棵树，并且所有测试用例的 $n$ 之和不超过 $2000$，$q$ 之和不超过 $2000$。

输出格式

对于每个测试用例，输出 $q$ 个整数，表示每个查询 $f(v_i, p_i)$ 模 $998\,244\,353$ 的结果。

形式上，令 $M = 998\,244\,353$。可以证明答案可以表示为不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12

1
6
6
2
4
9
8
15
2
3
6
9
5
5

说明/提示

在第一个测试用例中，树的结构如下：

第一个查询中，期望值为 $1$，因为机器人从顶点 $2$ 出发，一步就到达了顶点 $1$，过程结束。

第二个查询中的期望步数计算如下（$x$ 为步数）：

• $P(x < 2) = 0$，因为距离顶点 $1$ 是 $2$，机器人无法在更少的步数内到达。
• $P(x = 2) = \frac{1}{3}$，因为只有一种步骤序列使 $x = 2$。即 $3 \rightarrow_{1} 2 \rightarrow_{0.33} 1$，概率为 $1 \cdot \frac{1}{3}$。
• $P(x \bmod 2 = 1) = 0$，因为机器人只能通过偶数步数到达顶点 $1$。
• $P(x = 4) = \frac{2}{9}$：可能路径为 $3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$。
• $P(x = 6) = \frac{4}{27}$：可能路径为 $3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$。
• 一般情况下，$P(x = i \cdot 2) = \frac{2^{i - 1}}{3^i}$。

因此，$f(v, p) = \sum_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6$。

第二个测试用例中，树的结构如下：