描述
在一片由树形迷宫组成的奇幻森林里，所有道路连通成一棵无根树，我们将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 $。
样例
- 复制
- 复制
提示
在第一个测试用例中，树的结构如下：
第一个查询中，期望值为 $ 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 $。
第二个测试用例中，树的结构如下：
关注我们
